I am having trouble figuring out how to solve this recurrence problem...

$$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{aligned} $$

I lose the trail here and I cannot figure out how to finish it and actually find the complexity. Can anyone help? How can this be done?

  • 1
    $\begingroup$ Use the master theorem. Alternatively, you're almost there. What is the value of $k$ for which $n/2^k = 1$? Take it from there. $\endgroup$ – Yuval Filmus Jun 24 at 9:33
  • $\begingroup$ @YuvalFilmus thanks for your answer. That would be, $\log(n)$ if I am not mistaken. I thought that might be the next step from reading about the Master theorem ... but I know the final runtime of the recurrence is $O(n^2)$ and it seems like the solution you lead me to says it is $O(n \log n)$. Did I miss something? $\endgroup$ – deltaskelta Jun 24 at 12:46
  • 1
    $\begingroup$ A recurrence doesn't have a runtime. Also, if $f(n) = O(n^2)$, this doesn't preclude the possibility that $f(n) = O(n\log n)$. Recall that big O is just an upper bound. It doesn't have to be tight. $\endgroup$ – Yuval Filmus Jun 24 at 12:49
  • $\begingroup$ Furthermore, you seem to be missing the base case. Suppose that $T(1) = 1$. What does $4^k T(n/2^k)$ equal to when $k = \log_2 n$? $\endgroup$ – Yuval Filmus Jun 24 at 12:49
  • $\begingroup$ would it be $4^{\log_2 n}$? $\endgroup$ – deltaskelta Jun 25 at 1:21

Your Answer

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

Browse other questions tagged or ask your own question.