The master theorem can be used in case of a recurrence relation of the form

1) $T(n) = aT(\frac{n}{b}) + f(n)$

My question is whether it can be applied if

2) $\frac{T(n)}{g(n)} = aT(\frac{n}{b}) + f(n)$.

My gut feeling is that is should be possible: just solve equation 2 by solving equation 1, and then multiply the asymptotic bound I receive by $g(n)$

I just can't prove it

  • $\begingroup$ That’s obviously wrong because T(n)*g(n) wouldn’t fulfil the recurrency relationship. $\endgroup$ – gnasher729 Mar 30 '20 at 8:11
  • $\begingroup$ Take for example $g(n) = n$, $a = 1$, $b = 2$, $f(n) = 0$. The answer is $n^{\Theta(\log n)}$. How do you get this from the master theorem? $\endgroup$ – Yuval Filmus Mar 30 '20 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.