# Solving Recurrence Equations containing two Recursion Calls

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)$.

• If you have a recurrence of that form, there MUST be a base case, say $T(n) \leq 42$ for all $n < 100$. If not, then there's no saying what the recurrence will solve to: maybe $T(n) = 2^m$ for all $n < 100$, where $m$ is the size of the original problem! (imagine a recursion that ends in comparing the constant number of whatever you're recursing on to all subsets of the original elements) In other words: no base case implies not enough information to solve the recurrence. – Alex ten Brink May 6 '12 at 10:49

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)$.

You can use the more general Akra-Bazzi method.

In your case, we would need to find $p$ such that

$$\frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$$

(which gives $p \approx 1.364$)

and we then have

$$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$$

Note that you don't really need to solve for $p$. All you need to know is that $1 \lt p \lt 2$.

A simpler method would be to set $T(x) = x^2 g(x)$, and try proving that $g(x)$ is bounded.

Let $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ be a shorthand for the right-hand side of the recurrence. We find an lower and upper bound for $f$ by using $T(n/3) \leq T(n/2)$:

$$3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$$

If we use the lower resp. upper bound as right-hand side of the recurrence, we get $T'(n) \in \Theta(n^2)$ in both cases by the Master theorem. Thus, $T(n)$ is bounded from above by $O(n^2)$ and from below by $\Omega(n^2)$ or, equivalently, $T(n) \in \Theta(n^2)$.

1. For a complete proof, you should prove that $T$ is an increasing function.
• – Raphael May 10 '12 at 15:22
• That trick won't work for similar recurrences, like $T(n) = 2T(n/2) + 3T(n/3) + n^2$, that can be solved with recursion trees. (But even recursion trees won't work for $T(n) = 2T(n/2) + 4T(n/3) + n^2$, which can be solved with Akra-Bazzi.) – JeffE May 10 '12 at 19:45