# Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

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.

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

Who is right?

• @RohitSingh The title of a question should avoid using LaText/MathJax. Please check this. Commented Apr 25, 2022 at 16:04

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

• 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 Commented Apr 22, 2022 at 23:04

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