# trouble solving the recurrence 4T(n/2) + n

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?

• 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. – Yuval Filmus Jun 24 at 9:33
• @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? – deltaskelta Jun 24 at 12:46
• 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. – Yuval Filmus Jun 24 at 12:49
• 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$? – Yuval Filmus Jun 24 at 12:49
• would it be $4^{\log_2 n}$? – deltaskelta Jun 25 at 1:21