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

Question

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?

Answer 1

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<k$ and $p\geqslant0$
  Answer is $\theta({n^k}({\log n})^p)$

• If $\log_ba<k$ 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)

$$\theta(n^2)$$