I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):


$r$ is independent of $n$. Case 1 of the Master theorem applies and tells us that $T(n)=O(n^2)$.

However, this hides a constant dependent on $r$ in the big-oh notation: our recurrence has depth $O(\log_2 n)$ so at the final level we have $O(4^{\log_2 n})=O(n^2)$ subproblems, each of which takes $O(r)$ time to be handled. This means the actual running time is $O(n^2 r)$ (or worse: this analysis only talks about the lowest level).

This is my actual recursion:


Is there a method similar to the Master theorem for these kinds of recursions?

  • $\begingroup$ If $r$ is constant $O(nr) = O(n)$, but if you looking for exact time this is different thing. $\endgroup$
    – user742
    Commented Apr 29, 2012 at 18:24
  • $\begingroup$ It is probably possible to generalize the Master's theorem to multiple parameters. $\endgroup$
    – Kaveh
    Commented Apr 29, 2012 at 18:36

1 Answer 1


Use a recursion tree (otherwise known as the proof of the Master Theorem). I'll assume here that $r>1$, since otherwise the recurrence never bottoms out.

  • The root of the recursion tree for $T(n)$ has value $nr^2$.

  • The root has $r^2$ children, each with value $(n/r)r^2 = nr$. Thus, the total value of all children is $nr^3$.

  • Each child has $r^2$ children of its own, each with value $(n/r^2)r^2 = n$. Thus, the total value of all grandchildren of the root is $nr^4$.

  • An easy induction argument implies that for any integer $\ell\ge 0$, the root has $r^{2\ell}$ descendants at level $\ell$, each with value $(n/r^\ell)r^2 = nr^{2-\ell}$. Thus, the total value of all nodes at level $\ell$ is $r^{2\ell} \cdot nr^{2-\ell} = nr^{2+\ell}$.

  • The level sums $T(n) = nr^2 + nr^3 + \cdots + nr^{2+\ell} + \cdots$ form an increasing geometric series, so (for big-Oh purposes) only the deepest level matters.

  • The recursion reaches its base case when $n/r^\ell = 1$, or equivalently, when $\ell = \log_r n$.

  • The total value of all nodes at that level is $nr^{2+\ell} = nr^{2+\log_r n} = n^2r^2$.

  • We conclude that $T(n) = O(r^2 n^2)$.

These notes describe the recursion tree method in more detail, with lots of examples.

Equivalently, define $S(n) = T(n)/r^2$, so that $S(n) = r^2 T(n/r) + n$, and then use the Master theorem to solve for $S(n)$. But that would require remembering the Master theorem, which I don't.

  • $\begingroup$ Saw the question and immediately thought "let's post a link to Jeff's notes". Naturally, you beat me to it : P $\endgroup$
    – Lucas Cook
    Commented Apr 29, 2012 at 19:23
  • $\begingroup$ Assuming the original recursion had $\Theta(nr^2)$, the result would also be sharp, i.e. $\Theta(r^2n^2)$, right? $\endgroup$
    – Raphael
    Commented Apr 30, 2012 at 7:55
  • $\begingroup$ Yes, that's right. $\endgroup$
    – JeffE
    Commented Apr 30, 2012 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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