6 pts 1. In the definition of Big-O, why is the "for N >= n0" needed? 6 pts 2. If f1(N) = 2N and f2(N) = 3N, why are they both O(N), since 3N is larger than 2N for N>=1? 6 pts 3. If a function is known to be O(N), what would you expect to happen to the running time if the input size is doubled? What if the function was O(N*N)? Explain your answer. 6 pts 4. Since Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analysis? 6 pts 5. Which grows faster, 2^n or n! ? Why? 10 pts (2 each) 6. Give the Big-O notation for the following expressions: a. 4n^5 + 3n^2 - 2 b. 5^n - n^2 + 19 c. (3/5)*n d. 3n * log(n) + 11 e. [n(n+1)/2 + n] / 2 Questions 7-12 are 10 points each. Assume numItems has the role of N, which may vary from one run to the next. 7. What is the Big-O running time for this code? Explain your answer. for (int i=0; i 0) i = i / 2; // integer division will eventually reach zero 12. What is the Big-O running time for this code? Explain your answer. public static int div(int numItems) { if (numItems == 0) return 0; else return numItems%2 + div(numItems/2); }