0

Master method usually deals with the equation having the following form :

$$T (n) = aT (n/b) + f(n)$$

But what if my equation is like this?

$$T( n) = T(5n/7) + n $$

How can I find the tight asymptotic bound for such equations?

The n inside the T function isn't alone. I have a constant 5 with it. So I am actually confused.

Simran Munot
  • 1

1 Answers1

0

Assume that $T_n=a+b n+c n^2$ and replace $$T( n) - T(5n/7) - n=\frac{2 b n}{7}-n+\frac{24 c n^2}{49}$$ So, $c=0$ and $b=\frac 72$ and then $$T_n=a+\frac 72 n$$

Claude Leibovici
  • 260,315