Big-O, Omega and Theta Notations

Big-$O$ notation

Definition: “$f(n)$ is big-$O$ of $g(n)$” or $f(n)$ = $O(g(n))$, if there are two positive constants $c$ and $n0$ such that $f(n) ≤ c g(n)$ for all $n ≥ n0$,

In other words, $c g(n)$ is an upper bound for $f(n)$ for all $n ≥ n0$. The function $f(n)$ growth is slower than $c g(n)$. For a sufficiently large value of input $n$ ...