Solving Recurrence relation: T(n) = 3T(n/5) + lgn * lgn

Question

Consider the following recurrence
T(n) = 3T(n/5) + lgn * lgn

What is the value of T(n)?

(A) Theta(n ^ log_5{3})
(B) Theta(n ^ log_3{5})
(c) Theta(n Log n )
(D) Theta( Log n )

Answer is (A)

My Approach :

lgn * lgn = theta(n) since c2lgn < 2*lglgn < c1*lgn for some n>n0

Above inequality is shown in this picture for c2 = 0.1 and c1 = 1

log_5{3} < 1,

Hence by master theorem answer has to be theta(n) and none of the answers match. How to solve this problem??

Answer 1

Your claim that lg n * lg n = Θ(n) is false. Notice that the limit of (lg n)² / n tends toward 0 as n goes to infinity. You can see this using l'Hopital's rule:

lim_{n → ∞} (lg n)² / n

= lim _{n → ∞} 2 lg n / n

= lim _{n → ∞} 2 / n

= 0

More generally, using similar reasoning, you can prove that lg n = o(n^ε) for any ε > 0.

Let's try to solve this recurrence using the master theorem. We see that there are three subproblems of size n / 5 each, so we should look at the value of log₅ 3. Since (lg n)² = o(n^{log₅ 3}), we see that the recursion is bottom-heavy and can conclude that the recurrence solves to O(n^{log₅ 3}), which is answer (A) in your list up above.

Hope this helps!

Answer 2

To apply Master Theorem we should check the relation between

n^log₅(3) ~= n^0.682 and (lg(n))²

Unfortunately lg(n)² != 2*lg(n): it is lg(n²) that's equal to 2*lg(n)

Also, there is a big difference, in Master Theorem, if f(n) is O(n^log_b(a)-ε), or instead Θ(n^log_ba): if the former holds we can apply case 1, if the latter holds case 2 of the theorem.

With just a glance, it looks highly unlikely (lg(n))² = Ω(n^0.682), so let's try to prove that (lg(n))² = O(n^0.682), i.e.:

∃ n₀, c ∈ N⁺, such that for n>n₀, (lg(n))² < c * n^0.682

Let's take the square root of both sides (assuming n > 1, the inequality holds)

lg(n) < c₁ * n^0.341 , (where c₁ = sqrt(c))

now we can assume, that lg(n) = log₂(n) (otherwise the multiplicative factor could be absorbed by our constant - as you know constant factors don't matter in asymptotic analysis) and exponentiate both sides:

2^lg(n) < 2^{c₂ * n0.341} <=> n < 2^{c₂ * n0.341} <=> n < (n^20.341)^c₂ <=> n < (n^20.341)^c₂ <=> n < (n^1.266)^c₂

which is immediately true choosing c₂ = 1 and n₀ = 1

Therefore, it does hold true that f(n) = O(n^log_b(a)-ε), and we can apply case 1 of the Master Theorem, and conclude that:

T(n) = O(n^log₅3)

Same result, a bit more formally.