# Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel like I am not getting the big picture. Right now I am just trying around until I find something that seems plausible.

Here is what I have tried so far:

Problem: Prove that $T(n) = \theta(n^2)$ where $T(n) = \frac{n(n+1)}{2}$

My Approach: I know that T(n) is $\theta(n^2)$ if $T(n) = O(n^2)$ and $n^2 = O(T(n))$ both apply, if I can prove both, the statement is therefore true.

1. In order to proof $T(n) = O(n^2)$, I check if $\lim\limits_{n\to \infty}\frac{T(n)}{n^2}$ exists, which it does: $\lim\limits_{n\to\infty}\frac{n(n+1)}{\frac{2}{n^2}} =\lim\limits_{n\to\infty} \frac{\frac{1}{2}n^2+\frac{1}{2}n}{n^2}=\lim\limits_{n\to\infty}\frac{1}{2}+\frac{1}{2n}=\frac{1}{2}$

2. To prove that $n^2=\theta(T(n))$ I argue that $n^2 \le 2 * \frac{n(n+1)}{2}=n^2+n$ and that therefore, for all $c =2>0$ and for all $n \ge n_0 = 1:n^2 \le c *T(n)$ applies $n^2 = O(T(n))$

• Yes, the two asymptotic estimates in your title are equivalent. Commented Apr 9, 2018 at 7:59
• Thanks for the clarification! Is there sort of an "all in one" proof for this type of problem, or is this the most efficient way to solve it? Commented Apr 9, 2018 at 8:03
• Asymptotic estimates like this are usually simply taken for granted. After seeing the proof once, there is no reason to do it ever again. Commented Apr 9, 2018 at 8:05
• If you are bent on doing an actual proof, you can use $\frac{n(n+1)}{2} = \frac{n^2}{2} + O(n) = \frac{n^2}{2} + o(n^2) = \Theta(n^2)$. Commented Apr 9, 2018 at 11:08
• Great, thanks again! Feel free to post your comment(s) as an answer, so I can mark them as helpful. Commented Apr 9, 2018 at 12:38

It follows from the definitions that $f(n) = O(g(n))$ iff $g(n) = \Omega(f(n))$, in the same way that $a \leq b$ is equivalent to $b \geq a$. Therefore in order to prove $f(n) = \Theta(g(n))$, it suffices (and necessary) to prove $f(n) = O(g(n))$ and $g(n) = O(f(n))$.
The "quick" way to prove that $\binom{n}{2} = \Theta(n^2)$ is $$\binom{n}{2} = \frac{1}{2} n^2 + O(n) = \frac{1}{2} n^2 + o(n^2) = \Theta(n^2),$$ where the last equality is a general result: $cf(n) + o(f(n)) = \Theta(f(n))$.
In practice, we take the following fact as well-known: if $P$ is a polynomial whose leading coefficient is positive then $$P(n) = \Theta(n^{\deg P}).$$ Using this, you can immediately deduce $\binom{n}{2} = \Theta(n^2)$.