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