Directed Reading C++ for You ++
pp.464-468 Asymptotics: Big-O Notation

  1. 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?

  2. Why does "one step" in a sequential search take less time than "one step" of a binary search?

  3. If an array contains 75 elements, how many comparisons are made in the worst case for
        a. a sequential search?
        b. a binary search?

  4. Sequential search time grows ________ while binary search time grows ________.

  5. For large n, rank these orders of growth from best (smallest) to worst (largest):
    O(n2), O(n), O(log2n)

Continue to:  Unit 2  / Prev  / Next