Asymptotic Notation

Provides the math function to represent bounds on time and space complexity for big inputs.

Big O Notation (O): Upper bound.
- Most useful and easiest to calculate.
Big Theta Notation (Θ): Upper and lower bound.
Big Omega Notation (Ω): Lower bound.

$$ \lim_{{x \to \infty}} f(x)=O(g(x)) $$

$f(x)$ is a function to analyze the complexity of as the inputs reach infinity.

The popular complexities:

Function	Complexity	Example
$O(1)$	Constant	Reading an element from an array
$O(\log n)$	Logarithmic	Search
$O(n)$	Linear	Searching an unordered array
$O(n \log n)$	Linearithmic	Sorting
$O(n^2)$	Quadratic	Nested Loops
$O(2^n)$	Exponential	Brute-force
$O(n!)$	Factorial	Traveling salesman

Example:

for i in 0..n {
    for j in 0..n {
        // some arbitrary unit of space or time complexity
    }
}

This is $O(n^2)$.

After counting the arbitrary unit, take away constant terms and coefficients.

Suppose there’s an array that is iterated through n times and each time an item is removed until none are left. That’d be $O(\frac{1}{2}n^2) = O(n^2)$.

The smaller terms become trivial for large inputs.

If there are independent inputs, they can’t be simplified out so we might have $O(nm)$.