Calculating complexity for recursive functions with substitution method (Big O notation)

Question

(https://i.sstatic.net/oTCBO87A.png) I have to calculate the complexity of this algorithm using the substitution method but I don't understand how to do it.

I'm guessing that T(n)=O(n^2). So I tried to prove it. T(n)=O(n^2) means that exists some c such as T(n)<=cn^2 for all n>=n0. I assume that this is true for all m<n. I take m=n/2<n so I assume that T(n/2)<=c(n/2)^2. Now I try to substitute. 4T(n/2) + kn <= 4c(n/2)^2 + kn = cn^2 + kn cn^2+kn should be <= cn^2 but this is only true for k<0. What am I doing wrong? Can k be less than 0? Am I doing something wrong in the calculation or my guess is wrong?

Answer 1

Your guess is right. By the Master Theorem, $T(n)=O(n^{2})$ is definitely true. Your substitution is false because the assumption is an inequality and thus We have $T(n) \leq cn^2$ and $T(n) = 4T(n/2) +kn \leq cn^2 + kn$. It is not a contradiction, but simply a failed proof.

See CLRS’s Introduction to Algorithms, which is a good reference for solving recursive equations by substitution and the powerful Master Method.

Answer 2

Your inductive hypothesis should be $T(n)<=cn^2-dn$, for $c,d>0$. Assume that the hypothesis is true for all $m<n$, we have \begin{align}T(n)&=4T(\frac{n}{2})+\Theta(n)\\&\le 4(c(\frac{n}{2})^2-d\frac{n}{2})+\Theta(n)\\&\le cn^2-2dn+\Theta(n)\\&\le cn^2-dn-(dn-\Theta(n))\\&\le cn^2-dn,\end{align} as long as $d$ is chosen larger than the hidden coefficient in $\Theta(n)$.

Adding $-dn$ into the hypothesis is the key of the proof.

For more information, you ought to reference CLRS about substitution method, as well as the Master theorem, the free pdf could be easily found on the Internet. My proof is mainly based on the book.