Introduction to Java Programming, Seventh Edition, Y. Daniel Liang
Chapter 23 Algorithm Efficiency
Section 23.2 Estimating Algorithm Efficiency
1
Estimating algorithm efficiency is ________
A.
to measure their actual execution time.
B.
to estimate their execution time.
C.
to estimate their growth function.
2
What is the number of iterations in the following loop:
int count = 5;
while (count < n) {
count = count + 3;
}
A.
n - 5
B.
n - 3
C.
n / 3 - 1
D.
(n - 5) / 3
E.
the ceiling of (n - 5) / 3
3
An input that results in the shortest execution time is called the _____________.
A.
best-case input
B.
worst-case input
C.
average-case input
4
Why is the analysis often for the worst case?
A.
Best-case is not representative.
B.
Worst-case is not representative, but worst-case analysis is very useful. You can show that the algorithm will never be slower than the worst-case.
C.
Average-case analysis is ideal, but difficult to perform, because it is hard to determine the relative probabilities and distributions of various input instances for many problems.
5
O(1) is ________.
A.
constant time
B.
logarithmic time
C.
linear time
D.
log-linear time
6
Which of the following complexity is O(nlogn)
A.
300n + 400n*n
B.
23nlogn + 50
C.
45n + 45nlogn + 503
D.
n*n*n + nlogn
7
On an average, linear search searches
A.
the whole list
B.
half of the list
C.
just one element in the list
D.
one fourth of the list
8
For a sorted list of 1024 elements, a binary search takes at most _______ comparisons.
A.
11
B.
100
C.
512
D.
6