Common Time Complexities
Ordering of common algorithmic growth rates.
Formula
Variables
Example
For large n, an O(n log n) sort crushes an O(n²) one — e.g. millions vs trillions of steps.
How it works
These Big-O classes are arranged by how quickly the amount of work grows as the input size n increases. Constant time stays essentially flat, logarithmic time grows very slowly, linear time grows in direct proportion to n, and the later classes become progressively more expensive because they add extra passes, pairwise comparisons, or branching possibilities. This ordering comes from comparing dominant growth rates for large n: any fixed constant is eventually smaller than log n, which is eventually smaller than n, then n log n, then n², and exponential growth outpaces them all.
When to use it
Use this ordering when you want to compare algorithms, estimate scalability, or decide whether a solution will remain practical as data gets large. It is especially useful in interviews, algorithm design, and performance analysis of search, sorting, graph, and recursive problems.
Worked example, step by step
Suppose an algorithm with input size n = 1,000 has these operation counts: O(1): 1 operation O(log n): log2(1000) ≈ 10 operations O(n): 1,000 operations O(n log n): 1,000 × 10 = 10,000 operations O(n^2): 1,000^2 = 1,000,000 operations O(2^n): 2^1000 operations, which is unimaginably large and impossible to compute directly So the ranking for n = 1,000 is: 1 < 10 < 1,000 < 10,000 < 1,000,000 << 2^1000 This matches the general order O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n).
Common mistakes to avoid
- Treating Big-O as an exact runtime instead of an upper-bound growth rate
- Assuming n log n is always closer to n than to n² for all n, without checking the actual input size
- Forgetting that exponential algorithms become infeasible very quickly even when n seems small
Did You Know?
An O(n²) algorithm on a million items does a trillion operations — why algorithm choice matters enormously.
Share this formula
More in Computer Science
View allShannon Entropy
AdvancedAverage information content of a random source (bits).
Master Theorem (form)
AdvancedAnalyzes running time of divide-and-conquer algorithms.
Hamming Distance
AdvancedNumber of positions at which two strings differ.
Bits to Represent n
BasicMinimum number of bits to represent n distinct values.
Binary to Decimal
BasicConverts a binary number to decimal.
Nodes in a Full Binary Tree
IntermediateTotal nodes in a perfect binary tree of height h.