1. Using e-notation, provide asymptotically tight bounds in terms of n for the s
ID: 3883115 • Letter: 1
Question
1. Using e-notation, provide asymptotically tight bounds in terms of n for the solution to each of the following recurrences. Assume each recurrence has a non-trivial base case of T(n) (1) for all n S no where no is a suitably large constant. For example, if asked to solve T(n) = 2T(n/2) + n, then your answer should be (n log n). Give a brief explanation for each solution. Giving only the upper or lower bound (using big-oh or big- notation) may be worth partial credit. (a) T(n) 8T(n/2) n3 (b) T(n)- 5T(n/3)+ n (c) T(n) = T(n-1) + (d) T(n)=T(n/2) +27(n/5)+1 (e) T(n)-TW) + T(J i) + lg nExplanation / Answer
a) T(n) = 8T(n/2) + n3
We can use Masters theorem to solve this problem, Lets compare it with T(N) = aT(N/b) + f(n)
=> a = 8 , b = 2, f(n) = n3
= > nlogb a = nlog2 8 = n3
=> Since nlogb a is equal to f(n), By Case 2 of Masters theorem we get
T(n) = (n3 log n)
b) T(n) = 5T(n/3) + n
We can use Masters theorem to solve this problem, Lets compare it with T(N) = aT(N/b) + f(n)
=> a = 5 , b = 3, f(n) = n
= > nlogb a = nlog3 5 = n1.46
=> Since nlogb a is >= to f(n), By Case 1 of Masters theorem we get
T(n) = (nlogb a) = (n1.46)
c) T(n) = T(n-1) + n2
We can use Substitution method to solve this problem
=> T(n-1) = T(n-2) + (n-1)2
=> T(n) = T(n-2) + (n-1)2 + n2
=> T(n-2) = T(n-3) + (n-2)2
=> T(n) =T(n-3) + (n-2)2 + (n-1)2 + n2
=> T(n) =T(1) + .... + (n-2)2 + (n-1)2 + n2
=> It boils down to SUmmation of n2 terms
= n(n+1)(2n+1) / 6
=> T(n) = (n3 )
Thanks, let me know if there is any concern.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.