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.


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}$
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&gt;0$ and for all $n \ge n_0 = 1:n^2 \le c *T(n)$ applies $n^2 = O(T(n))$
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)$.