Asymptotic Notation: Big O, Omega, and Theta

Understanding efficiency is paramount in algorithmic analysis and computational complexity. For example, how do engineers measure the performance of an algorithm as the input size grows? This is where asymptotic notation shines, serving as the linguistic bridge that allows developers to discuss the scalability and efficiency of algorithms. It provides descriptive language and mathematical representations of function growth rates, allowing for informed comparisons of algorithms. Asymptotic notation and algorithmic efficiency help process massive datasets, deliver real-time responses, and optimize resources.

This blog post examines the language of efficiency and explores the significance of asymptotic notation.

🌸👋🏻 Join 10,000+ followers! Let’s take this to your inbox. You’ll receive occasional emails about whatever’s on my mind—offensive security, open source, academics, boats, software freedom, you get the idea.

Big O notation (O)

TLDR: Describes an upper bound on the growth rate of an algorithm’s running time. It represents the worst-case scenario.

One type of asymptotic notation is Big O. It describes the performance or complexity of an algorithm in terms of time and space.

Big O provides a high-level understanding of how an algorithm’s runtime or space requirements grow as the input size increases. The “O” in Big O stands for “order,” and the notation describes the upper bound of an algorithm’s growth rate.

used on a post about asymptotic notation

View graph on Desmos

Analyzing algorithm efficiency

Big O notation simplifies comparing and analyzing algorithms by focusing on their fundamental behavior rather than the exact implementation details. Here are some classic growth rates or time complexities.

Examples

Constant
- The algorithm’s runtime remain constant regardless of the input size. Constant time is the most desirable scenario.
- O(1) or $O(1)$
- $f(n) = c$ where $c$ is a positive constant.
Logarithmic
- The algorithm’s efficiency grows logarithmically as the input size increases. Examples include binary search algorithms.
- O(log n) or $O(\log n)$
- $f(n) = c \cdot \log_b(n)$
Linear
- The algorithm’s runtime grows linearly with the input size. Examples include simple linear searches.
- O(n) pr $O(n)$
- $f(n) = c \cdot n$
Linearithmic – also known as linear logarithmic
- Common in efficient sorting algorithms like merge sort and heap sort.
- O(n log n) or $O(n \log n)$
- $f(n) = c \cdot n \cdot \log_b(n)$
Polynomial
- The algorithm’s runtime is proportional to the $k$ -th power of the input size, where $k$ is a constant. Some examples directly below show the algorithm’s best-case performance grows with the square or cube of the input size. Common in nested loops.
- O(n^2), O(n^3), …, O(n^k) or $O(n^2)$ , $O(n^3)$ , …, $O(n^k)$
- $f(n) = c \cdot n^2$ , $f(n) = c \cdot n^3$ , … $f(n) = c \cdot n^k$
- The general form of a polynomial function is $f(n) = a_k \cdot n^k + a_{k-1} \cdot n^{k-1} +$ … $+ a_1 \cdot n + a_0$ , where $n$ is the input size and $a_k, a_{k-1}, \ldots, a_1, a_0$ are constants.
Exponential
- The algorithm’s runtime doubles with each addition to the input size. Note anything below this point is highly inefficient. These algorithms have growth rates that quickly become impractical for large inputs.
- O(2^n) or $O(2^n)$
- $f(n) = c \cdot 2^n$
Factorial
- The algorithm’s runtime grows factorial with the input size.
- O(n!) or $O(n!)$
- $f(n) = c \cdot n!$

Omega notation (Ω)

TLDR: Omega notation represents a lower bound on the growth rate of an algorithm’s running time. It describes the best-case scenario.

While Big O notation provides an upper bound on the growth rate of algorithms, Omega notation—another type of asymptotic notation—complements it by offering insight into lower bounds. Omega notation, represented by the Greek letter Ω, describes the lower bound or best-case scenario of an algorithm’s performance in terms of time or space complexity. Similar to Big O notation, Omega notation helps express how the performance of an algorithm scales with the input size, but it focuses on the lower limit.

Omega notation helps engineers create efficient algorithm designs. It allows developers to identify situations where an algorithm exhibits optimal performance and assures that the algorithm will not perform better in these cases.

Analyzing lower bounds

Omega notation classifies algorithms based on their lower bounds, providing a hierarchy similar to how Big O notation classifies them based on upper bounds. Some common Omega notations or lower bounds include:

Constant
- The algorithm’s best-case performance remains constant, regardless of the input size.
- Ω(1) or $\Omega(1)$
Logarithmic
- The algorithm’s best-case efficiency grows logarithmically with the input size.
- Ω(log n) or $\Omega(\log n)$
Linear
- The algorithm’s best-case performance grows linearly with the input size.
- Ω(n) or $\Omega(n)$
Linearithmic – also known as linear logarithmic
- Common in algorithms with optimal sorting performance.
- Ω(n log n) or $\Omega(n \log n)$
Polynomial
- The algorithm’s runtime is proportional to the $k$ -th power of the input size, where $k$ is a constant. Some examples directly below show the algorithm’s best-case performance grows with the square or cube of the input size.
- Ω(n^2), Ω(n^3), …, Ω(n^k) or $\Omega(n^2)$ , $\Omega(n^3)$ , …, $\Omega(n^k)$
Exponential
- The algorithm’s runtime doubles with each addition to the input size. Note anything below this point is highly inefficient. These algorithms have growth rates that quickly become impractical for large inputs.
- Ω(2^n) or $\Omega(2^n)$
Factorial
- The algorithm’s runtime grows factorial with the input size.
- Ω(n!) or $\Omega(n!)$

Theta notation (Θ)

TLDR: Theta notation represents both upper and lower bounds. It provides a tight bound on the growth rate.

The last type of asymptotic notation is Theta notation. Theta notation describes both the upper and lower bounds of an algorithm’s performance. It signifies a tight, asymptotically tight, or optimal bound, providing a more precise understanding of an algorithm’s behavior than Big O or Omega notation alone.

While Big O notation characterizes the upper limit or worst-case scenario, and Omega notation deals with the lower limit or best-case scenario, Theta notation captures the sweet spot—the range where an algorithm’s efficiency is asymptotically tight from above and below. In simpler terms, Theta notation defines an algorithm’s “just right” growth rate.

Theta notation is particularly valuable when developers want a more accurate representation of an algorithm’s behavior across different inputs. It offers a balanced perspective by considering the best and worst-case scenarios. In other words, it provides a more nuanced understanding of algorithmic efficiency.

Analyzing growth rates

Theta notation is typically expressed in the form $\Theta(g(n))$ , where “g(n)” represents the growth rate of the algorithm. Some time complexity examples include:

Constant
- The algorithm’s performance is constant in the best and worst-case scenarios.
- Θ(1) or $\Theta(1)$
Logarithmic
- The algorithm’s efficiency grows logarithmically with the input size, with tight bounds from above and below.
- Θ(log n) or $\Theta(\log n)$
Linear
- The algorithm’s performance grows linearly with the input size, and the upper and lower bounds match.
- Θ(n) or $\Theta(n)$
Linearithmic – also known as linear logarithmic
- Common in efficient sorting algorithms like merge sort, exhibiting a tight range of growth.
- Θ(n log n) or $\Theta(n \log n)$
Polynomial
- The growth rate follows a polynomial curve, with matching upper and lower bounds. The algorithm’s runtime is proportional to the $k$ -th power of the input size, where $k$ is a constant. Some examples directly below show the algorithm’s best-case performance grows with the square or cube of the input size.
- Θ(n^2), Θ(n^3), …, Θ(n^k) or $\Theta(n^2)$ , $\Theta(n^3)$ , …, $\Theta(n^k)$
Exponential
- The algorithm’s runtime doubles with each addition to the input size. Note anything below this point is highly inefficient. These algorithms have growth rates that quickly become impractical for large inputs.
- Θ(2^n) or $\Theta(2^n)$
Factorial
- The algorithm’s runtime grows factorial with the input size.
- Θ(n!) or $\Theta(n!)$