# Master method recurrence question [duplicate]

This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below).

For a recurrence of $$T(n) = a T(\frac{n}{b}) + f(n)$$

where f(n) is $\Theta{(n)}$, would we be comparing $n^{\log_b(a)}$ with $n^{1}$ - meaning we would be comparing $log_b(a)$ with 1? Since the rate of growth is linear?

what about where f(n) is $\Theta{(1)}$ (aka some constant?), would we be comparing $n^{\log_b(a)}$ with $n^{0}$? '0' since there is no rate of growth for a constant?

• Don't worry about the proposed duplicate. In a nutshell, the answers to both of your questions is "yes". – Rick Decker Nov 5 '15 at 20:04
• I don't see what this question is asking that is not answered by (carefully) reading the theorem itself. Okay, maybe if $1 = n^0$, but that's self-evident (assuming high-school mathematics). Hence, I'm closing as duplicate of our reference question, which contains a statement of the theorem with examples. If that doesn't solve your problem, please edit to clarify what that is, exactly. – Raphael Nov 6 '15 at 8:09

I think the question is asking how to translate $f(n)$ into Big-Theta notation to be used for the Master Theorem. You have the right idea about switching between notations.
$T(n) = aT(n/b) + \Theta(n^d)$
So, yes, if you have a linearly growing function, then $f(n)$ may be substituted with $\Theta(n)$.