2
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

$\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.