# 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. Jun 24, 2020 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?
– Joff
Jun 24, 2020 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. Jun 24, 2020 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$? Jun 24, 2020 at 12:49
• would it be $4^{\log_2 n}$?
– Joff
Jun 25, 2020 at 1:21

We can use Master Theorem to solve this :

If a Recurrence Relation is of the Form

## $$T(n)=aT\bigg(\frac{n}{b}\bigg)+{n^k}({\log(n)})^p$$

Then, as per Master Theorem, we have Six Conditions depending on value of $$a,b,k$$ and $$p$$

• If $$\log_ba>k$$
Answer is $$\theta(n^{\log_ba})$$

• If $$\log_ba=k$$ and $$p>-1$$
Answer is $$\theta({n^k}({\log n})^{p+1})$$

• If $$\log_ba=k$$ and $$p=-1$$
Answer is $$\theta({n^k}\log\log n)$$

• If $$\log_ba=k$$ and $$p<-1$$
Answer is $$\theta(n^k)$$

• If $$\log_ba and $$p\geqslant0$$
Answer is $$\theta({n^k}({\log n})^p)$$

• If $$\log_ba and $$p<0$$
Answer is $$\theta({n^k})$$

In any problem, our main motive is to find $$a,b,k$$ and $$p$$.

In Given Problem
$$a=4$$
$$b=2$$
$$k=1$$
$$p=0$$

Now, $$\log_24 = 2$$ which is greater than $$k$$ $$(1)$$ Therefore, Answer is $$\theta(n^{\log_ba})$$

Putting Value(s)