patternMinor
Master theorem and constants independent of $n$
Viewed 0 times
independentmastertheoremandconstants
Problem
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?
$$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?
Solution
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.
-
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.
Context
StackExchange Computer Science Q#1576, answer score: 7
Revisions (0)
No revisions yet.