15
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Alex ten Brink May 6 '12 at 10:49
15
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – Raphael May 10 '12 at 15:22
  • 1
    $\begingroup$ 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.) $\endgroup$ – JeffE May 10 '12 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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