In algorithmic analysis, how do engineers measure an algorithm’s performance as the input size grows? With asymptotic notation. It provides language and mathematical representations of function growth rates, so developers can compare algorithms. Asymptotic notation and algorithmic efficiency help process massive datasets, deliver real-time responses, and optimize resources.
This post covers Big O, Omega, and Theta notation.
Read more: Algorithm Development and Analysis.
🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.
Big O notation (O)
TLDR: Describes an asymptotic upper bound on a function’s growth rate. It is commonly used to state worst-case running time, but O itself is not “the worst case.”
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.

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
where
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
- Linear
- The algorithm’s runtime grows linearly with the input size. Examples include simple linear searches.
- O(n) or
- Linearithmic – also known as linear logarithmic
- Common in efficient sorting algorithms like merge sort and heap sort.
- O(n log n) or
- Polynomial
- The algorithm’s runtime is proportional to the
-th power of the input size, where
is a constant. Some examples directly below show runtimes that grow with the square or cube of the input size. Common in nested loops.
- O(n^2), O(n^3), …, O(n^k) or
,
, …,
,
, …
- The general form of a polynomial function is
, where
is the input size and
are constants, with
.
- The algorithm’s runtime is proportional to the
- 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
- Factorial
- The algorithm’s runtime grows factorial with the input size.
- O(n!) or
-
Want your company or product in front of [ret]2read readers?
One sponsor per issue →
Omega notation (Ω)
🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.
TLDR: Omega notation represents a lower bound on the growth rate of an algorithm’s running time. It gives an asymptotic lower bound and can be applied to the best, average, or worst case.
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 an asymptotic lower bound on an algorithm’s performance in terms of time or space complexity, and it can be applied to the best, average, or worst case. 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 guarantees the running time grows at least as fast as the stated bound.
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 running time is at least a constant, regardless of the input size.
- Ω(1) or
- Logarithmic
- The running time grows at least logarithmically with the input size.
- Ω(log n) or
- Linear
- The running time grows at least linearly with the input size.
- Ω(n) or
- Linearithmic – also known as linear logarithmic
- Common in algorithms with optimal sorting performance.
- Ω(n log n) or
- Polynomial
- The algorithm’s runtime is proportional to the
-th power of the input size, where
is a constant. Some examples directly below show runtimes that grow at least with the square or cube of the input size.
- Ω(n^2), Ω(n^3), …, Ω(n^k) or
,
, …,
- The algorithm’s runtime is proportional to the
- 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
- Factorial
- The algorithm’s runtime grows factorial with the input size.
- Ω(n!) or
🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.
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 gives an asymptotically tight bound: when
is both
and
, 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 and Omega notation deals with the lower limit, Theta notation applies when the two match: the function is bounded from above and below by the same growth rate. It applies to one function (e.g. the worst-case running time), not to the spread between best and worst cases. In simpler terms, Theta notation defines an algorithm’s “just right” growth rate.
Theta notation is useful when developers want to state exactly how a given running time grows, such as the worst-case running time, rather than only an upper or lower limit. It pins that growth rate down from both sides.
Analyzing growth rates
Theta notation is typically expressed in the form , 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
- Logarithmic
- The algorithm’s efficiency grows logarithmically with the input size, with tight bounds from above and below.
- Θ(log n) or
- Linear
- The algorithm’s performance grows linearly with the input size, and the upper and lower bounds match.
- Θ(n) or
- Linearithmic – also known as linear logarithmic
- Common in efficient sorting algorithms like merge sort, exhibiting a tight range of growth.
- Θ(n log n) or
- Polynomial
- The growth rate follows a polynomial curve, with matching upper and lower bounds. The algorithm’s runtime is proportional to the
-th power of the input size, where
is a constant. Some examples directly below show runtimes that grow with the square or cube of the input size.
- Θ(n^2), Θ(n^3), …, Θ(n^k) or
,
, …,
- The growth rate follows a polynomial curve, with matching upper and lower bounds. The algorithm’s runtime is proportional to the
- 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
- Factorial
- The algorithm’s runtime grows factorial with the input size.
- Θ(n!) or
Asymptotic notation
Big O gives upper bounds, Omega gives lower bounds, and Theta gives tight bounds; each can be applied to best-, average-, or worst-case analysis.
Developers use these notations to compare algorithm designs and set realistic expectations. If you enjoyed this post on asymptotic notation, consider reading Algorithm Development and Analysis.


You must be logged in to post a comment.