Search code examples
algorithmrecurrence

Solving a recurrence relation using iteration method

Consider this example : 

T(n) = T(7n/8) + 2n

I assumed T(1) = 0

and tried to solve it in the following way 

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)

but I could not come to any conclusion about this. I am confused about what should I do in the next step.

Solution

  • Your approach is sound, but you'll see what to do if you rewrite it slightly differently:

    T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

    Now, let k tend to infinity and see what happens. It would help if you're familiar with geometric series.