3
$\begingroup$

Given the recurrence

$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$

My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with the substitution method.

recurrence

So $T(n)$ is $\leq cn$ for every $c\geq4$. So in my opinion $T(n)$ is $O(n)$.

Who is right?

$\endgroup$
1
  • $\begingroup$ @RohitSingh The title of a question should avoid using LaText/MathJax. Please check this. $\endgroup$
    – John L.
    Commented Apr 25, 2022 at 16:04

2 Answers 2

5
$\begingroup$

You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$.

Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{O}(n\log n)$.

$\endgroup$
1
  • $\begingroup$ Yes, sure, the professor's solution is correct but not the best. Anyway, I have used the substitution method and not the Akra Bazzi method, I've updated my question with an image of the substitution step $\endgroup$
    – Bender
    Commented Apr 22, 2022 at 23:04
2
$\begingroup$

Let $n=2^m$. The recurrence is written

$$T(2^m)=2T(2^{m-3})+2T(2^{m-2})+2^m$$

or

$$U(m)=2U(m-3)+2U(m-2)+2^m.$$

A particular solution is given by $U=c2^m$ and more precisely

$$c=2\frac c8+2\frac c4+1,$$ giving $c=4$.

Then the characteristic polynomial of this ordinary linear recurrence has three roots with a modulus smaller than $2$ (https://www.wolframalpha.com/input?i=roots+of+x%5E3-2x-2%3D0) and the homogeneous response becomes neglectable compared to the particular solution.

Hence the solution is indeed asymptotic to $2^m=n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.