2
$\begingroup$

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

  1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

  2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

Improve this question
$\endgroup$
9
  • $\begingroup$ "Exact asymptotics" typically refers to $\sim$, not $\Theta$. $\endgroup$
    – Raphael
    Commented Jul 4, 2017 at 22:37
  • $\begingroup$ "as far as I can see an unsolvable equation" -- Huh? You have $>$ for $p=1$ and $<$ for $p=3$, and both sides are continuous functions -- there certainly is a solution! (Tools find it for you.) $\endgroup$
    – Raphael
    Commented Jul 4, 2017 at 22:39
  • 1
    $\begingroup$ The recursion tree approach is difficult because you get an unbalanced tree. See JeffE's notes on Recursion Trees specifically page 9, Ham Sandwich Trees. Next take a look at using Domain Transformations. Check out 5.3 in these notes. You might have some luck with a domain transformation of $t(k) = T(\frac{3^k}{2^k})$. From there I was able to get $t(k) \leq 2t(k-1) + 3t(k-3)$, but haven't gotten a tight recurrence. $\endgroup$
    – ryan
    Commented Jul 5, 2017 at 0:37
  • 1
    $\begingroup$ It seems that the Akra–Bazzi theorem gives you the answer you want. The number $p$ does have a closed form – it is the unique solution of $2+2^{p+1}=3^p$. There well might be no better closed form. $\endgroup$
    – Yuval Filmus
    Commented Jul 5, 2017 at 2:26
  • 1
    $\begingroup$ If this is "only" about solving for $p$, the question may be better suited for Mathematics. Let me know if you want us to migrate it there! $\endgroup$
    – Raphael
    Commented Jul 5, 2017 at 5:31

1 Answer 1

Reset to default
-2
$\begingroup$

Completely unscientifically, the 2T (N/3) can be ignored. The 2T (2N/3) doubles whenever N is multiplied by 1.5, which starting with T(1) happens log N / log 1.5 times, so the result is about $2^{\log N / \log 1.5}$ or $N^{\log 2 / \log 1.5}$ which is about $N^{1.709}$. The n that is added is less than this, so $\Theta(N^{1.709})$ is my unscientific answer.

It just so happens that $p = \log 2 / \log 1.5 = 1.709$ also solves your equation $2 + 2^{p+1} = 3^p$. At least up to 9 decimals according to my spreadsheet.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Isn't dropping "dominated" terms dangerous? My gut complains that whether they change the result may depend on which case of the master theorem, so to speak (leaves dominate, inner nodes dominate, both dominate), you hit. $\endgroup$
    – Raphael
    Commented Jul 5, 2017 at 10:57
  • $\begingroup$ Unfortunately, this answer is wrong. 1.709 comes close to solving it, but it fails after a couple decimal places. The actual value of p is about 2.196. $\endgroup$
    – Retired account
    Commented Jul 5, 2017 at 13:13

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.