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!
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!