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

Improve this question
$\endgroup$
1
  • 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
    Commented May 6, 2012 at 10:49

3 Answers 3

Reset to default
16
$\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)$.

Improve this answer
$\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.

Improve this answer
$\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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ let us continue this discussion in chat $\endgroup$
    – Raphael
    Commented May 10, 2012 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
    Commented May 10, 2012 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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