# Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

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 ﬁrst 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.

1. "$$O(n^2)$$ is indeed an upper bound for the recurrence" means $$T(n) \in O(n^2)$$. That is, $$\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \le c n^2$$.
2. "$$\Omega(n^2)$$ must be a lower bound for the recurrence" means $$T(n) \in \Omega(n^2)$$. That is $$\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \ge c n^2$$.
4. Yes. In this step you use induction to show that $$T(n) \le d n^2$$ for some choice of a constant $$d > 0$$.
• I was a bit confused with exact meaning as to whether they are using the asymptotic notation in the usual set sense as $O(n^2)$ is a set after all, or as an anonymous function. Thanks for the help. The statement is quite odd to interpret as the first meant a "set is an upper bound bound for the recurrence" and the second interpretation (as a function) as I thought which ultimately leads to what you said if we use the transitivity property for the Big Oh or Big Omega... Jun 19, 2020 at 18:16