Complexity Analysis.md

title	date	lastmod
Complexity Analysis	2022-11-08	2022-11-21

Complexity Analysis

Asymptotic Notations

Notations used to describe the order of growth of a given function

Big-O $O(f(x))$

The limits when taking the 2 functions to infinity produces a constant C that $$\begin{align}\lim_{n\to \infty}\frac{f(n)}{g(n)}=C \ C=0 \ or\ 0<C<\infty \end{align}$$

Big-Omega $\Omega(f(x))$

The limits when taking the 2 functions to infinity produces a constant C that $$\begin{align}\lim_{n\to \infty}\frac{f(n)}{g(n)}=C \ C=\infty \ or\ 0<C<\infty \end{align}$$

Big-Theta $\theta(f(x))$

The limits when taking the 2 functions to infinity produces a constant C that $$\begin{align}\lim_{n\to \infty}\frac{f(n)}{g(n)}=C \ 0<C<\infty \end{align}$$

Properties

$$f(n)\in O(h(n)),g(n)\in O(h(n)) \implies f(n)+g(n)\in O(h(n))$$

Example function comparisons

Order of Common Functions

Specific Complexities

• Polynomial Time Complexity
• Pseudo-Polynomial Time Complexity