# Does this recurrence relation run in $\Theta(n)$?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this recurrence relation) to $\sqrt{2} * c * n + 32 * \sqrt{2} * n - 32$, which runs in tight bounds $\Theta(n)$. Can you guys confirm this? I’ll show more of my work if this answer is incorrect.

• Did you mean $T(1) = c$? Even so, this would only make sense if $n$ is always a power of $4$.
– MBW
Apr 24 '15 at 19:14
• For a complete solution you should get $$T(n) = 2^{\log_4 n} T(1) + 16 \left(2^{\log_4(n)-1} - 1\right)$$ start with $S(n) = T(4^n)$ and solve the recursion for $S$. Apr 24 '15 at 19:32
• @PedroVeras Yeah I fix that. Thanks! Apr 24 '15 at 20:40

Following Wikipedia's notation for the master theorem, you have $a=2,b=4,f(n)=16$. So $\log_b(a)=\log_4(2)=1/2$, so $f(n)=O(n^{\log_b(a)})$. So we are in case 1, and $T(n)=\Theta(n^{1/2})$. So somewhere you made a mistake.
My issue was that I simplified $2^{\frac{log_2n}{2}}$ as $2^{\frac12}*2^{log_2n}$, not $(2^{log_2n})^{\frac12}$. If I used the exponential rule correctly, I would have gotten $\theta(n^{\frac12})$.