3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, the two asymptotic estimates in your title are equivalent. $\endgroup$ – Yuval Filmus Apr 9 '18 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 Apr 9 '18 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$ – Yuval Filmus Apr 9 '18 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$ – Yuval Filmus Apr 9 '18 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 Apr 9 '18 at 12:38
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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