2. 3- What is the growth of the below function: (What is the most accurate answer?)

   () = 2^(^3) + + 7^6 + ^2 options: a) (n) b) (n3) c) (n2logn) d) (n) e) (log6n)

3. What is the growth of the below function: (What is the most accurate answer?) () = + 4^2 + ^2 options: a) O (logn) b) O (loglogn) c) O (log2n) d) O(logn2) e) Neither

4. 5- Assume you want to write a code to calculate the multiplication of two numbers. Provide the running time for your algorithm, assuming the inputs are two n-digit numbers. Explain your answer.

5. 6- Suppose a machine on average takes 10-6 seconds to execute a single algorithm step. What should be the largest input size to finish in 1s ?

   for(i=1; i <= n*n; i++) linear_search(a , key); //size(a) = n, and key is the last element in a

6. 7- What is the largest value of n such that an algorithm whose running time is 5nlog2n runs faster than an algorithm whose running time is 35log2n on the same machine?

7. Prove that () = 2^2 + 2^3 + 2^() is O(n^2logn), provide the appropriate C and k constants.

8. 9- Compare the growth of f(n) = + 2^ and g(n) =

9. 10- Prove transitivity of big-O: if f(n) = O(g(n)), then g(n) = (f(n)).

10. 11- Prove that if () ()/() = 4, then f(n)= (g(n)).

11. 12- What is the growth of n^2 + 2n^2 + 3n^2 + + n^4?

12. Prove that if f(n) is monotonically decreasing, then

    () = ((1 to n) ())

    =1

13. 14- Suppose g(n) 1 for all n, and that f(n) g(n) + L, for some constant L and all n. Prove that f(n) = O(g(n)).

14. 15- Given a sorted array with n integers, provide an algorithm with the running time of O(logn) that checks if there is an i for which a[i]= 5i. (e.g. a = [1 4 10 12 17 21] >> true because a[2] = 2*5 = 10) (Explain your answer)

15. 16- Prove or disprove: ()! = (()^^2)