patternModerate
Solving Recurrence Equations containing two Recursion Calls
Viewed 0 times
callscontainingsolvingequationsrecursionrecurrencetwo
Problem
I am trying to find a $\Theta$ bound for the following recurrence equation:
$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$
I figure Master Theorem is inappropriate due to differing amount of subproblems and divisions. Also recursion trees do not work since there is no $T(1)$ or rather $T(0)$.
$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$
I figure Master Theorem is inappropriate due to differing amount of subproblems and divisions. Also recursion trees do not work since there is no $T(1)$ or rather $T(0)$.
Solution
Yes, recursion trees do still work! It doesn't matter at all whether the base case occurs at $T(0)$ or $T(1)$ or $T(2)$ or even $T(10^{100})$. It also doesn't matter what the actual value of the base case is; whatever that value is, it's a constant.
Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.
-
The root of the recursion tree has value $n^2$.
-
The root has three children, with values $(n/2)^2$, $(n/2)^2$, and $(n/3)^2$. Thus, the total value of all children is $(11/18) n^2$.
-
Sanity check: The root has nine grandchildren: four with value $(n/4)^2$, four with value $(n/6)^2$, and one with value $(n/9)^2$. The sum of those values is $(11/18)^2 n^2$.
-
An easy induction proof implies that for any integer $\ell\ge 0$, the $3^\ell$ nodes at level $\ell$ have total value $(11/18)^\ell n^2$.
-
The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
-
We conclude that $T(n) = \Theta(n^2)$.
Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.
-
The root of the recursion tree has value $n^2$.
-
The root has three children, with values $(n/2)^2$, $(n/2)^2$, and $(n/3)^2$. Thus, the total value of all children is $(11/18) n^2$.
-
Sanity check: The root has nine grandchildren: four with value $(n/4)^2$, four with value $(n/6)^2$, and one with value $(n/9)^2$. The sum of those values is $(11/18)^2 n^2$.
-
An easy induction proof implies that for any integer $\ell\ge 0$, the $3^\ell$ nodes at level $\ell$ have total value $(11/18)^\ell n^2$.
-
The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
-
We conclude that $T(n) = \Theta(n^2)$.
Context
StackExchange Computer Science Q#1682, answer score: 16
Revisions (0)
No revisions yet.