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))$

  • $\begingroup$ Yes, the two asymptotic estimates in your title are equivalent. $\endgroup$ Commented Apr 9, 2018 at 7:59
  • $\begingroup$ 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? $\endgroup$
    – Lucky
    Commented Apr 9, 2018 at 8:03
  • $\begingroup$ Asymptotic estimates like this are usually simply taken for granted. After seeing the proof once, there is no reason to do it ever again. $\endgroup$ Commented Apr 9, 2018 at 8:05
  • $\begingroup$ 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)$. $\endgroup$ Commented Apr 9, 2018 at 11:08
  • $\begingroup$ Great, thanks again! Feel free to post your comment(s) as an answer, so I can mark them as helpful. $\endgroup$
    – Lucky
    Commented Apr 9, 2018 at 12:38

1 Answer 1


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.