Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.
(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text while solving the recurrence and the statements are given as ordered list at the end. Simply because I want to master the text.)
$$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$$
Now the authors attempt to first find a good guess of the recurrence relation using the recursion tree method and for that they allow sloppiness and assumes $T(n)=3T(n/4) + cn^2$.
Though the above recursion tree is not quite required for my question but I felt like including it to make the background a bit clearer.
The guessed candidate is $T(n)=O(n^2)$. Then the authors proof the same using the substitution method.
In fact, if $O(n^2)$ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The first recursive call contributes a cost of $\Theta(n^2)$ , and so $\Omega(n^2)$ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ We want to show that $T(n)\leq d n^2$ for some constant $d > 0$.
Now there are a few things which I want to get clarified...
(1) if $O(n^2)$ is indeed an upper bound for the recurrence. Here the sentence means (probably) $\exists$ a function $f(n) \in O(n^2)$ such that $T(n)\in O(f(n))$
(2) $\Omega(n^2)$ must be a lower bound for the recurrence Here the sentence means probably $\exists$ a function $f(n) \in \Omega(n^2)$ such that $T(n)\in \Omega(f(n))$
(3) $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ This sentence can be interpreted as follows assume that $T'(n) = 3T'(\lfloor n/4 \rfloor) + cn^2$ and $\exists$ a function $T(n) \in O(n^2)$ such that $T'(n)\in O(T(n))$
(4) $T(n)\leq d n^2$ for some constant $d > 0$ We are using induction to verify to the definition of Big Oh...
I feel that the author could simply have written the $T(n)$ is Upper Bounded by $n^2$ and Lower Bounded by $n^2$ or the author could have simply written $T(n) = O(n^2)$ and $T(n)=\Omega(n^2)$, did the author just use the above style of statements as pointed out in $(1),(2),(3)$ just for more clearer explanation or there are some extra meaning conveyed which I am missing out.