Directed Reading C++ for You ++
pp.464-468 Asymptotics: Big-O Notation
- If the target is randomly chosen from the n values in the array, state how many comparisons
will be made on average
a. in a sequential search?
b. in a binary search?
- Why does "one step" in a sequential search take less time than "one step" of a binary search?
- If an array contains 75 elements, how many comparisons are made in the worst case for
a. a sequential search?
b. a binary search?
- Sequential search time grows ________ while binary search time grows ________.
- For large n, rank these orders of growth from best (smallest) to worst (largest):
O(n2), O(n), O(log2n)
Continue to: Unit 2