1. Consider the following recurrence. T(n) = T([n/2])+2T([n/8])+n n8, and T(n) = 1 1n <8. One can prove that T(n) = O(n). Do you

  

1. Consider the following recurrence. T(n) = T([n/2])+2T([n/8])+n n8, and T(n) = 1 1n 0. Consider the recurrence T(n)T([cn])+ T([cn]) + T([czn])+an, n>1/c, T(n) = 1 n1/c. Prove by induction that T(n) = O(n). More precisely show that T(n) an + b for n 1 where a, b > 0 are some fixed but suitably chosen constants (you get to choose and fix them based on C1, C2, C3, ). You may first want to try the concrete recurrence at the start of the problem. How does a depend on C1, C2, C3? Consider the recursion tree for the recurrence. What is an asymptotic upper bound on the depth of the recursion tree? Express this as a function of n and C1, C2, C3. You do not need to prove correctness of your bound. We now consider a somewhat more general setting. Let 0 < c c... Ck < 1 bek rationals such that C 0. Suppose we have a recurrence of the form k T(n) = T([cn])+an, n1/c,T(n)=1 n1/c. i=1 You can show that T(n) = O(n) via induction as in the simpler case when k = 3. State the bound for a in this more general setting and also the depth of the recursion as a function of n, C1, C2,..., Ck. You do not need to prove correctness of your bound.