# Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n [duplicate]

I have no idea how to solve this one - I end up with $$\sum_{i=0}^k (2^k * 5 * 3^i)$$ but I have no clue how to get any further than that (e.g. resolve the sum even further, if it's even correct to begin with).

This is the task - masters theorem is not allowed:

T(n) = 2 * T(n/3) + 5n

T(1) = 5

and we know, that n = 3^k

We can use master's method to solve this.

a = 2
b = 3
n^(log(a)base(b)) = n^(log(2)base(3)) = n^(0.63)
Now, f(n) = 5n
f(n) > n^(0.63)
so,
if time complexity = T(n), then using master's theorem:
T(n) = Theta(5n) = Theta(n)

Without the use of master's theorem: using substitution method

T(n) = 2 * T(n/3) + 5n
= 2 * [2 * T(n/(3^2)) + 5(n/3)] + 5n
simplifying:
= (2^2) * T(n/(3^2)) + (2/3)5n + 5n
...
= (2^k) * T(n/(3^k)) + [(2/3)^(k-1)]*5n + ... + (2/3)^0 * 5n -----(1)
The value of k:
n/(3^k) = 1
k = log(n) base 3 ----- (2)
using (2) in (1)
= (2^k) * 5 + [(2/3)^(k-1)]*5n + ... + (2/3)^0 * 5n
= 5 * [(2^k) + [(2/3)^(k-1)] * n + ... + (2/3)^0 * n] ------ (3)
= 2^k = 2^(log n base 3) = n ^ (log 2 base 3) = n ^ 0.63 -------(4)
substituting (4) into (3)
= 5 * [(n^0.63) + n * {(2/3)^(k-1) + .... (2/3)^0}]
The term in {curly brace} is a GP, after solving it is O(1)
= 5 * [(n^0.63) + n*O(1)]
n * O(1) + (n ^ 0.63) = n
= 5 * n
Hence complexity, T(n) = O(n)
• First off - thanks a lot for your comment! But I totally forgot to mention, that I'm not allowed to use the master's theorem... – user2477349 Feb 6 at 15:51
• @user2477349 check the updated answer – Breakpoint Feb 6 at 16:09
• The master theorem is proved using the substitution method. It simply tells you what you get by applying it. If you’re using the substitution method, you’re just proving a special case of the master theorem. – Yuval Filmus Feb 6 at 16:43