Search code examples
algorithmmathbig-orecurrence

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

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

Solution

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

    limn → ∞ (lg n)2 / 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 log5 3. Since (lg n)2 = o(nlog5 3), we see that the recursion is bottom-heavy and can conclude that the recurrence solves to O(nlog5 3), which is answer (A) in your list up above.

    Hope this helps!