1. Consider the following recurrence. T(n) = T([n/2])+2T([n/8])+n n8, and T(n) = 1 1n 0....

  

Transcribed Image Text:

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 see that T(n) = (n)? The goal of this problem is to show a more general statement and to refresh your induction skills. Let C1, C2, C3 be rational numbers such that 0 < c c C3 and c + C+ C3 < 1. Let a > 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 <1. And a > 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. 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 see that T(n) = (n)? The goal of this problem is to show a more general statement and to refresh your induction skills. Let C1, C2, C3 be rational numbers such that 0 < c c C3 and c + C+ C3 < 1. Let a > 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 <1. And a > 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.

Answer rating: 100% (QA)

Lets tackle this problem step by st... View the full answer