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

Question

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?

Answer 1

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

Answer 2

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