Examples

• big-O for $f(n) = n!$
• $6n^2 +5nlog(n) \space \rightarrow \space O(n^3)$

Common Growth Functions

Big-Omega (Best Case)

Definition:

Let $f$ and $g$ be functions from $N$ to $R$,

$f(x)$ is $\Omega (g(x))$ if there exist constants $C > 0$ and $k$ such that $|f(x)|\space ≥ \space C|g(x)|$ for all integers $x > k$

Big-O and Big-Omega Connection:

• f(x) is $\Omega$(g(x)) if and only if g(x) is $O$(f(x))
• $6n^2 +5nlog(n) \space \rightarrow \space \Omega(n^2)$

Big-Theta (Exact Case)

Definition:

Let $f$ and $g$ be functions from $N$ to $R$,

$f(x)$ is $\Theta(g(x))$ if $f(x)$ is $O(g(x))$ and $f(x)$ is $\Omega(g(x))$

When f(x) is $\Theta$(g(x)), we say that…

• f(x) is of order g(x)
• f(x) and g(x) are of the same order
• g(x) is also $\Theta$(f(x))
• $6n^2 +5nlog(n) \space \rightarrow \space \Theta(n^2)$