0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you mean $T(1) = c$? Even so, this would only make sense if $n$ is always a power of $4$. $\endgroup$ – MBW Apr 24 '15 at 19:14
  • $\begingroup$ 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$. $\endgroup$ – DanielV Apr 24 '15 at 19:32
  • $\begingroup$ @PedroVeras Yeah I fix that. Thanks! $\endgroup$ – committedandroider Apr 24 '15 at 20:40
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.