Need help with a problem with algorithmic complexity

Question

Is $n^2 = O(n^3)?$

Is that true? How does one go about proving it.

If that's true, one can say that the time complexity of Bubble Sort is $O(n^3)$.

Answer 1

By definition of $O(\cdot)$ $n^2$ is $O(n^3)$ if $\ \exists \ x_0 \in \mathbb{R} \land \ \exists \ c >0$ such that: $$n^2 \leq c n^3 \ \forall \ n\geq x_0 \ ,$$ and it clearly holds, for instance with $x_0=1$ and $c=1$.

A more easy way to see it is that $n^2$ is $O(n^3)$ if $\frac{n^2}{n^3}=\frac{1}{n}$ is limited, which is clearly true. This definition is almost equivalent to the first one (it has some problems when the denominator is $0$) but it is easier to visualize.

Being big $O$ of something can be roughly seen as "being asymptotically similar or smaller ignoring lower-order terms".

Answer 2

Yes.

$n^2$ is $O(n^3)$, and also $O(n^4), O(n^5), O(n^e), O(e^n), O(e^{e^n}), \ldots$

In algorithms, when we say some algorithm is in $O(f(n))$ generally, we mean to say that $c \cdot f(n)$ is a good approximation of the upper bound of complexity in terms of known functions of $n$.

Thus, while all of the $O(n^4), O(n^5), \ldots$ are indeed upper bounds to complexity of bubble sort as per the definition of $O(\cdot)$, but the one that serves the intended message and is useful is $O(n^2)$.

But yes, if $f(n) \in O(g(n))$, then $O(f(n)) \subseteq O(g(n))$