To analyze the performance of algorithms, we need a few key definitions.
Time Complexity
The time complexity of an algorithm, $T(n)$, is a function representing the running time as a function of the input size $n$. For example, suppose you can add any two numbers in 1 second. Then adding 100 numbers takes 100 seconds. In this case, $T(n) = n$.
Big-O Notation
Big-O notation provides an upper bound on an algorithm’s performance. For any time complexity $T(n)$, we write $T(n) = O(g(n))$ if there exist positive constants $M$ and $n_0$ such that $T(n) \le M g(n)$ for all $n \ge n_0$. For example, if $T(n) = n^3 + 10n^2 + n + 27$, then $T(n) = O(n^3)$ with $M = 39$, $n_0 = 1$, since $T(n) \le 39n^3$ for $n \ge 1$. In practice, it suffices to find the dominant (fastest-growing) term of $T(n)$.
Asymptotic Approximation
Big-O can be chosen pessimistically: $T(n) = O(n^2)$ is valid even when $T(n) = O(n)$. For a tighter characterization, we say an algorithm’s complexity is asymptotically equivalent to $g(n)$ when $\lim\limits_{n \to \infty}\frac{T(n)}{M g(n)} = 1$ for some positive constant $M$.
Big-$\Omega$ Notation
Big-$\Omega$ notation is the lower-bound counterpart of Big-O. For any time complexity $T(n)$, we write $T(n) = \Omega(g(n))$ if there exist positive constants $M$ and $n_0$ such that $T(n) \ge M g(n)$ for all $n \ge n_0$.
Big-$\Theta$ Notation
Big-$\Theta$ notation is used when both upper and lower bounds are the same. We write $T(n) = \Theta(g(n))$ if there exist positive constants $M_1$, $M_2$, and $n_0$ such that $M_2 g(n) \le T(n) \le M_1 g(n)$ for all $n \ge n_0$. However, not every algorithm has a tight $\Theta$ bound: some algorithms’ performance varies significantly depending on the input, so a single $\Theta$ expression may not capture their complexity.
Amortized Complexity
Amortized complexity is a technique for analyzing algorithms whose cost varies across calls. Many algorithms do not have a clean $\Theta$ bound for every single operation. However, using only Big-O can be overly pessimistic. Amortized complexity distributes the total cost over all operations. For example, if an algorithm runs in $O(1)$ for $n$ steps and $O(n^2)$ for one step, the amortized complexity per step is $O!\left(\frac{n + n^2}{n+1}\right) = O(n)$.
Space Complexity
Space complexity measures how much memory an algorithm uses. All of the above notations (Big-O, $\Omega$, $\Theta$) apply to space complexity as well.