Master theorem and constants independent of $n$

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

$$T(n)=4T(n/2)+O(r)$$

$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:

$$T(n)=r^2T(n/r)+O(nr^2)$$

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

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

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.

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