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)