3

First of all give the definition of $O(n)$ and use it to demonstrate that:

$O(n) * O(n) = O(n^2)$

I know that this is true because:

$O(f(x))*O(g(x)) = O(f(x)g(x))$

but I don't know how to demonstrate it, even with the definition:

$$f(x) = O(g(x))$$ if $$lim_{x\to0}\frac{f(x)}{g(x)}= l \in R$$

Christian Giupponi
  • 687

1 Answers1

5

If $F = O(f)$ and $G = O(g)$, then there is some $M > 0$ such that $|F| \leq M|f|$ and $|G| \leq M|g|$; then $|FG| \leq M^{2}|fg|$ and hence $FG = O(fg)$. So $O(f)O(g) = O(fg)$.

Yes
  • 20,719