Time Complexity in $\theta$ Notation $$T(n) = 2T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 5$$
What is the time complexity of the given algorithm in $\theta$ notation.
Thanks in advance.
 A: The shift $S(n)=T(n)+\frac52$ yields 
$$S(n)=\color{red}{\bf 2}\cdot S(n/\color{green}{\bf 2})+S(n/\color{green}{\bf 4}),
$$
then a general result is that 
$$S(n)=\Theta(n^a),
$$ where $a$ solves the equation 
$$1=\color{red}{\bf 2}\cdot\color{green}{\bf 2}^{-a}+\color{green}{\bf 4}^{-a},$$ that is, 
$$a=\log_2(\sqrt2+1)\approx1.2715533.
$$
To prove this, proceed by induction, that is, assume that the property $$c\cdot n^a\leqslant S(n)\leqslant C\cdot n^a$$ holds for every $n\leqslant N-1$, for some suitable positive $c$ and $C$, and show that it holds for $n=N$ as well.
A: If $T(n)=2T\left(\frac n2\right)+T\left(\frac n4\right)+5$ then one expansion results in
$$T(n)=4T\left(\frac n4\right)+2T\left(\frac n8\right)+10+2T\left(\frac n8\right)+T\left(\frac n{16}\right)+5+5\\=4T\left(\frac n4\right)+4T\left(\frac n8\right)+T\left(\frac n{16}\right)+20$$
A second expansion brings
$$T(n)=8T\left(\frac n8\right)+4T\left(\frac n{16}\right)+20+8T\left(\frac n{16}\right)+4T\left(\frac n{32}\right)+20\\+2T\left(\frac n{32}\right)+T\left(\frac n{64}\right)+5+20\\
=8T\left(\frac n8\right)+12T\left(\frac n{16}\right)+6T\left(\frac n{32}\right)+T\left(\frac n{64}\right)+65$$
So we have an increasing number of terms per expansion, and apparent-quadratic behavior in the constant term $(5\cdot 1, 5\cdot 4, 5\cdot 13,\dots)$.  One more expansion should help clarify these behaviors:
$$T(n)=16T\left(\frac n{16}\right)+8T\left(\frac n{32}\right)+40+24T\left(\frac n{32}\right)+12T\left(\frac n{64}\right)+60\\+12T\left(\frac n{64}\right)+6T\left(\frac n{128}\right)+30+2T\left(\frac n{128}\right)+T\left(\frac n{256}\right)+5+65\\=
16T\left(\frac n{16}\right)+32T\left(\frac n{32}\right)+24T\left(\frac n{64}\right)+8T\left(\frac n{128}\right)+T\left(\frac n{256}\right)+200$$
If we follow the constant term further, we now have $5\cdot 1, 5\cdot 4, 5\cdot 13, 5\cdot 40.$  The pattern of these constants is emerging, and appears to be $O(n^4)$.  Continuing with the analysis in this direction should provide a satisfactory conclusion.
A: First of all note that this recurrence only depends on the number of bits of $n$ and not on their values, which simplifies things considerably.
Suppose we wish to solve
$$T(n) = 2T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 5$$
where we set $T(0)=0.$
We unroll the recursion to obtain an exact formula for all $n:$
$$T(n) = 5 \times \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
[z^j] \frac{1}{1-2z-z^2}.$$
Now the roots of $1-2z-z^2 = 2-(z+1)^2$ are at $$-1 \pm \sqrt{2}$$
and their inverses are
$$\rho_{1,2} = 1 \pm \sqrt{2}.$$
It follows that
$$[z^j]   \frac{1}{1-2z-z^2} = c_1 (1+\sqrt{2})^j + c_2 (1-\sqrt{2})^j.$$
Once we determine the coefficients we get
$$[z^j]   \frac{1}{1-2z-z^2} = 
\frac{2+\sqrt{2}}{4} (1+\sqrt{2})^j+\frac{2-\sqrt{2}}{4} (1-\sqrt{2})^j.$$
The conclusion is that the closed and exact formula for $T(n)$ is
$$5\times 
\frac{2+\sqrt{2}}{\sqrt{2}\times 4} ((1+\sqrt{2})^{\lfloor \log_2 n \rfloor+1}-1)-
5\times
\frac{2-\sqrt{2}}{\sqrt{2}\times 4} ((1-\sqrt{2})^{\lfloor \log_2 n \rfloor+1}-1).$$
If desired we may re-write this as
$$-\frac{5}{2}+
5\times 
\frac{2+\sqrt{2}}{\sqrt{2}\times 4} (1+\sqrt{2})^{\lfloor \log_2 n \rfloor+1}-
5\times
\frac{2-\sqrt{2}}{\sqrt{2}\times 4} (1-\sqrt{2})^{\lfloor \log_2 n \rfloor+1}.$$
It follows that the complexity from the dominant asymptotic term is
$$\Theta\left((1+\sqrt{2})^{\lfloor \log_2 n \rfloor}\right)
= \Theta\left(2^{\log_2(1+\sqrt{2})\times \log_2 n}\right)
= \Theta\left(n^{\log_2(1+\sqrt{2})}\right).$$
The exponent here on $n$ is $$ 1.271553303,$$confirming the analysis by @Did.
A similar Master Theorem calculation can be found at this MSE link.
