Solving T(n) = 2T(n/3) + 2 T(2n/3) + n

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.

• "Exact asymptotics" typically refers to $\sim$, not $\Theta$.
– Raphael
Jul 4, 2017 at 22:37
• "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.)
– Raphael
Jul 4, 2017 at 22:39
• 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.
– ryan
Jul 5, 2017 at 0:37
• 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. Jul 5, 2017 at 2:26
• 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!
– Raphael
Jul 5, 2017 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.