Part 1: Experiments

1.Billy and Danny are debating about the solution to thier sorting algorithms. Billy claims that his O(n log n)-time solution must always be faster than Dannys O(n2 ) solution. However, Danny claims that he ran a number of experiments on both algorithms on his laptop and sometimes his was faster. Explain why this might have happened.

1. Order the following functions by asymptotic growth rate: a. 5nlogn + 4n | 200n^3, | 10n + 2n | 4logn b. 6n | 7nlogn | 8n + 9 | 60000 ? n^6

c.. 2^100 | 2n^2 + 200n^2 | n^3 ? 2000 |n^90 |3^n-1 d. 63 | 4n| 3logn | 2^n+2 | 10^logn

Part 2 - Proof & Analysis

3. Give a good big-Oh characterization in terms of n of the running time of the following. Provide brief justification

for your answer by finding a suitable k and n0. a. n^4 + 3n b. 15n^16 + 3n log n + 2n c. 3logn + 2logn d. 12n * 3n - 50n

Part 3 - Proof & Analysis 4. Give a good big-Theta characterization in terms of n of the running time of the following. Provide brief justification for your answer (in terms of finding a k0, k1, and n0). a. 5 log n + 12n^2 b. 6n log n + 4n

5. Show that the following statements are true: a. 2^n+5 ? 0(2^n) b. n^2 ? ?(n log n)