I want to solve the following exercise:
Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2)+n^2$ is $\Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract off a lower-order term to make a substitution proof work." (In all the text lg means logarithm in base $2$.)
I was able to show the first part, that $T(n) \leq cn^2$ gave nothing interesting. I'm trying to do the second one. I want to do the $O$ and $Ω$ separately. I start with the $O$. I wrote this Let's put $T(n)\leq cn^2-f(n)$ where $f$ is a function of $n\in \mathbb N$.
We have $T(n) \leq 4(c(n/2)^2-f(n/2))+n^2 = 2cn^2-4f(n/2)+n^2$. We want to have $$-4f(n/2)+n^2 \leq -f(n) \Longleftrightarrow 4f(n/2)-n^2 \geq f(n).$$ Let's write the recurrence equation $g(n) = 4g(n/2)-n^2$ and try $g(n) \leq c'n\lg(n)$, $c'>0$ being a constant.
I write $g(n) \leq 4c'(n/2)\lg(n/2)-n^2 = 2c'n\lg(n/2)-n^2 = n(2c'\lg(n/2)-1/2n)$ And then I concluded by saying that we know we have $2c'\lg(n/2) = o(n)$, by definition this means that for any constant $r > 0$, there is a rank $n_0$ from which $r n > 2c'\lg(n/2)$ so $2c'\lg(n/2)-1/2n$ will end by becoming lower than $0$ and since $n$ is positive $n(2c'\lg(n/2)-1/2n)$ will end by becoming lower than $0$ for any possible $c' > 0$ from a certain rank. As $c'n\lg(n)$ will never be lower than $0$, I conclude that $g(n) \leq c'n\lg(n)$ We need to verify the base's cases. We can't verify for $g(1)$ because we have $c'1\lg(1) = 0$ which cant be greater than $g(1)$ but we can easily verify it for $g(2)$ and $g(3)$ with $g(2) = 2c'$ and $g(3) = 3c'\lg(3)$, $\lg(2)$ can be verified for any $c' \geq g(2)$ and $g(3)$ can be verified for any $c' \geq g(3)$ so we take $c' = \max(g(2),g(3))$.
The recurrence hypothesis is verified. The base's cases are verified so the solution is valid.
So $c'n\lg(n)$ is a solution to this "sub-recurrence", and we can take $f(n) = c'n\lg(n)$.
But when I try to write $T(n) = 4T(n/2)+n^2$ on WolframAlpha the website tells me that the solution is $n^2 \lg(n)$ but as we just saw it I found $T(n) \leq cn^2+c'n\lg(n) = O(n^2)$ which correspond to the exercise statement but WolframAlpha seems to say the statement is wrong and some people I met on discord seems to agree that the solution is not $O(n^2)$.
Can you help me please? Is my reasoning wrong or is it correct? If it is wrong why is it please?
Let $f(n)=T(n)/n^2$. Dividing the given recursion by $n^2$ gives $$f(n)=\frac{T(n)}{n^2}=\frac{T(n/2)}{n^2/4}+1=f(n/2)+1 \,,$$ so in particular, $f(2^k)=k+f(1)$ is unbounded, and $T(n)$ is asymptotic to $n^2(\log_2(n)+C) $ as $n$ grows.