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

Question

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.

Answer 1

I actually did most of the steps of solving this recurrence relation correctly. If anyone's having as similar issue, here is my 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})$.

Answer 2

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.