Solve the Recurrence T(n) = 4T(n/3) + n * cuberoot(n)
Favorites|Homepage
Subscriptions | sitemap
HOME > > Solve the Recurrence T(n) = 4T(n/3) + n * cuberoot(n)

Solve the Recurrence T(n) = 4T(n/3) + n * cuberoot(n)

[From: ] [author: ] [Date: 12-01-26] [Hit: ]
T(n) = Θ(n^(4/3)).I hope this helps!......
Assume T(1) = 1. Give the answer in Big Theta notation. From my understanding using Case 3 of the master method the answer is Theta(n * cuberoot(n)). Would appreciate if someone else could verify that.

-
This time, a = 4, b = 3, and f(n) = n^(4/3).

Since, log_b (a) = log₃ 4 < 4/3, so we use the third case.
Take ε = 4/3 - log₃ 4 > 0; so n^(1/3) = Ω(n^(log₃ 4 + ε)).

Next, note that 4(n/3)^(4/3) = (4 / 3^(4/3)) * n^(1/3); so we can take C = 4 / 3^(4/3) < 1.
Hence, 4 f(n/3) ≤ C f(n) for all n.

Hence, the Master Theorem implies that
T(n) = Θ(n^(4/3)).

I hope this helps!
1
keywords: Recurrence,the,Solve,cuberoot,Solve the Recurrence T(n) = 4T(n/3) + n * cuberoot(n)
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .