algorithms – How to solve recurrence T(n)


The title wouldn’t let me format correctly, so here’s a better formatting of the question: Show by induction that any solution to a recurrence of the form

T(n) ≤ 2T(n/3) + c log3n

is O(n log3 n).

Hoping someone can help me with the correct solution. I attempted two ways to get the solution (but I think that they’re both incorrect):

SOLUTION A, where log is log3:

T(n) ≤ 2T(n/3) + c log(n)

≤ 2 * ( k(n/3)log(n/3) ) + c log(n)

= (2/3)kn(log(n)-1) + (c)log(n)

= (2/3)(kn)log(n) = (2/3)kn + (c)log(n)

= ((2/3)kn + c)log(n) – (2/3)kn

SOLUTION B, where log is log3:

T(n) ≤ 2T(n/3) + c log(n)

≤ 2 * ( k(n/3)log(n/3) ) + c log(n)

= (kn – kn/3)(log(n) – 1) + (c)log(n)

= (kn)log(n) – (kn/3)log(n) – kn + (c)log(n)

= (kn)log(n) – (2/3)kn + (c – kn/3)log(n)