1. An algorithm takes 1 ms for input size 100. How long will it take for input size 500 (assuming that low-order terms are negligible) if the running time is: (a) linear (b) quadratic (c)cubic 2. Use the definition of O,2. 9, to (a) show that 3n +6 O(n) (b) show that 3n + 6 ?(n) (c) show that 3n + 6 en) (d) is 2+1 O(2")? Explain the reason 3. Use the definition of O to prove: If f(n) and g -O(n), then f +g-O(n) 4. Rank the following functions: 100, log n, log(n2), log log n, and logn. Explain reasons for your ranking