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.

  • $\begingroup$ "Exact asymptotics" typically refers to $\sim$, not $\Theta$. $\endgroup$ – Raphael Jul 4 '17 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 Jul 4 '17 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 Jul 5 '17 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 Jul 5 '17 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 Jul 5 '17 at 5:31

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.

  • $\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 Jul 5 '17 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 Jul 5 '17 at 13:13

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.