# 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. – Yuval Filmus Apr 9 '18 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? – Lucky Apr 9 '18 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. – Yuval Filmus Apr 9 '18 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)$. – Yuval Filmus Apr 9 '18 at 11:08
• Great, thanks again! Feel free to post your comment(s) as an answer, so I can mark them as helpful. – Lucky Apr 9 '18 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)$.