1

I need pointers or corrections on my proof procedure.

Prove $x^2 + 2x + 1 \in O(x^2)$:

$x^2 + 2x + 1 \le cx^2$

$1+2/x+1/x^2 \le c$

This inequality holds for $x \ge 1$ and $c \ge 4$. Thus $x^2+2x+1 \in O(x^2)$

  • 1
    That's a Big O ("Big Oh"), not a Big Omega ("Big $\Omega$"). Also, your proof is just fine if you reverse the order of the lines. So you should have $$\begin{align}1 + 2/x + 1/x^2 \leq 4 \quad \forall x \geq 1 \qquad &\Longrightarrow \qquad x^2 + 2x + 1 \leq 4x^2 \quad \forall x \geq 1 \ &\Longrightarrow \qquad |x^2 + 2x + 1| \leq 4 |x^2| \quad \forall x \geq 1\end{align}$$ which implies that $x^2+2x+1 \in O(x^2)$ on the domain $x \geq 1$. – Antonio Vargas Mar 17 '13 at 17:25

1 Answers1

1

Generally, Big O is determined from the #Formal_definition or by using the limit superior. Your way of determining is not conventional and rather adhoc

Formal definition of Big O $f(x) = O(g(x))$ $\iff$ there exists a positive real number M and a real number $x_0$ such that

$$|f(x)| \le M|g(x)| \forall x>x_0\tag1$$

So starting with your expression

$$|x^2 + 2x + 1|\le x^2 + 2x^2 + 1$$ $$\le x^2 + 2x^2 + x^2$$ $$\le 4x^2$$ $$\le 4|x^2|$$

So $$|x^2 + 2x + 1|\le 4|x^2|$$

Co relating with $(1)$, we have $$|x^2 + 2x + 1|\le 4|x^2| \forall x>1$$ where $M=4, x_0 = 1$ So $$f(x) = O(x^2), as\quad x\quad \to\infty$$

Abhijit
  • 2,544
  • Could you please elaborate where and why do you think my process falls short? I really did not get much from your answer. –  Mar 17 '13 at 16:13
  • 1
    @cRaZiRiCaN: I have added couple of lines to my answer for the reasoning of not supporting your approach – Abhijit Mar 17 '13 at 16:22