patternMinor
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Viewed 0 times
analysisasymptoticstackoverflow
Problem
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?
$$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?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#150930, answer score: 5
Revisions (0)
No revisions yet.