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: 


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