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

cs.stackexchange https://cs.stackexchange.com/questions/120401

  •  29-09-2020
  •  | 
  •  

Question

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

Thanks for all of your advice & help!

Was it helpful?

Solution

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)
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top