Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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