Chapter 19 Exercise Set 2: Big-O Exercises

1. Read Big O Notation Tutorial – A Guide to Big O Analysis.

2. Read Writing a big-O proof in Building Blocks for Theoretical Computer Science by Margaret M. Fleck. Then prove that \(2n^2 + 5n - 8\) is \(O(n^2)\).

3. If you know that the element you are looking for is somewhere in the unordered array you are searching through, then the probability is you will find it after looking through about half the elements in the array. Explain why \(\frac{n}{2}\) is \(O(n)\).