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?


marked as duplicate by user340082710, David Richerby, Ran G., Raphael Nov 6 '15 at 8:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Don't worry about the proposed duplicate. In a nutshell, the answers to both of your questions is "yes". $\endgroup$ – Rick Decker Nov 5 '15 at 20:04
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

Another way to write the Master Theorem is as follows:

$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)$.

Then you may proceed with your comparisons.

  • $\begingroup$ I don't understand what you're trying to say, here. What's the relationship between your statement of the Master Theorem and the line following it? $\endgroup$ – David Richerby Nov 5 '15 at 23:00
  • $\begingroup$ @DavidRicherby Note the difference between your post's definition of T(n) and mine. Both are acceptable forms, although I think the one I have written is more useful to your question. So say your function f(n) grows linearly, you may substitute d = 1 into my statement, as you hypothesized. $\endgroup$ – jblakeley Nov 6 '15 at 23:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.