# Possible to use master method on T(n)/g(n)=aT(n/b)+f(n)

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

• That’s obviously wrong because T(n)*g(n) wouldn’t fulfil the recurrency relationship. – gnasher729 Mar 30 '20 at 8:11
• 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? – Yuval Filmus Mar 30 '20 at 11:42