COMP 4700 Algorithms Assignment #2 Growth of functions All of the work should be submitted as a softcopy. No hardcopy will be accepted Questions should be submitted in one file in pdf format. Name the file as LASTNAME-HW2 submit it through eLearn. If the file is not named as instructed, 20 points will be deducted 1. 2. 3. 4. Due date is 09/21/2017 at 11:30PM 5. The system will close after 5:30PM and you will not be able to turn it in. So, make sure you submit by due date and time Q1) show that (n2+1) (n+1) is O(n) Q2) Sort the following running time functions in an ascending asymptotic order. /2, 1 000log(n), nlog(n), 2n!, 2n, 3n, 1.1n, /1000 Q3) Is nlog(n) = (n) ? Is 2n = (n)? Explain your answer for each one Q4) Find the big-O notation for the following running time functions a) T(n) = ( + 8)(n+2) b) T(n) = (nlog(n) + ) ( 3) c) T(n) = 3n(5 + 210g(r)) d) T(n) = log(2n) + 2n + r? Q5) Prove using the definition of big-O notation that either 3 0(2") or not. Q6) let T(n) be a running time function defined recursively as T(n)- 1, n=1 3T (n 1)- 2T(n -2), n1 a) Find a non-recursive formula for T(n) b) Prove by induction that your answer in part (a) is correct c) Find a tight bound for T(n) Q7) Find the running time function of the following algorithms as we learned in the class and then the tightest big-O notation a) AlgorithmX(n) b) AlgorithmY(n) c) AlgorithmZ(n) for i1 to n for j 1 toy? return x for i1 to n 2. 4, 6. 2. 2. for i1 to n 4.while j<>