Question 2: (20 points) (a) Prove that the following function is e(n'). T(n) 4n -50n5 100n3 +500n +1000 logz n + 10. (b) Prove the following tight bound for log n! log(nl) logi e(n log n). Hints: The upper bound is proved by observing that log i S log n for all i. For the lower bound, you may consider only the larger n/2 terms in the summation. That is, , logi2 ;-[n/2] log i Question 3: (30 points) Use induction to prove each of the following: i-1 (b) Sum of squares