Common Complexities
Overview
The common complexity classes form a hierarchy of growth rates that virtually all algorithms fall into: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), and O(n!). Each class represents a qualitatively different scaling regime — moving one step up the hierarchy can mean the difference between an algorithm finishing in milliseconds or not finishing in your lifetime.
Knowing the hierarchy lets you immediately judge whether an algorithm is feasible for a given input size. When an interviewer says n can be up to 10^5, you instantly know O(n^2) is borderline and O(n^3) is impossible, and you need an O(n log n) or O(n) approach.
Where used: Constraint-based algorithm selection in competitive programming and interviews, Load testing and capacity planning: will this O(n log n) sort handle 10 million records within our SLA?
Why learn this
- It provides the mental ruler that makes every future complexity analysis instant — you stop calculating and start recognizing.
- The constraint-to-complexity mapping (n <= 10^6 means you need O(n log n) or better) is used in virtually every timed coding assessment.
- It reveals why certain classes of problems are fundamentally intractable: O(2^n) on n = 50 is more operations than atoms in the universe.
Aha moment
# How long does each take if one operation = 1 nanosecond?
# n = 100
# O(n) = 100 ns (instant)
# O(n log n) = 664 ns (instant)
# O(n^2) = 10,000 ns (instant)
# O(2^n) = 1.27 * 10^21 ns = 40,000+ YEARS
# n is just 100. Not a million. One hundred.Prediction: O(2^n) on n = 100 will take maybe a few minutes at most.
Common guess: All complexities are manageable when n is only 100.
O(2^100) is approximately 1.27 * 10^30 operations. At a billion operations per second, that is 4 * 10^13 years — thousands of times longer than the age of the universe. Exponential growth does not just slow down your program; it makes it physically impossible to complete. This is why NP-hard problems are fundamentally different from polynomial ones.
Common mistakes
- Assuming O(n log n) is 'basically O(n)': While log n grows slowly, it is NOT a constant. At n = 10^9, log2(n) is about 30 — so an O(n log n) algorithm does 30 billion operations versus 1 billion for O(n). That 30x factor can push you past the time limit.
- Forgetting that O(n^2) explodes faster than intuition suggests: At n = 1000, O(n^2) means a million operations — fine. At n = 100,000, it means 10 billion operations — likely too slow. The jump from 'works on test cases' to 'times out on the judge' is exactly this transition.
- Not recognizing O(1) amortized vs. O(1) worst-case: A dynamic array append is O(1) amortized but O(n) worst-case (when it resizes). Confusing these can lead to incorrect analysis of tight inner loops or real-time systems.
Glossary
- qualitatively different
- Differing fundamentally in kind or nature rather than just in amount.
- fundamentally intractable
- Practically impossible to solve for large inputs because it would take too long.
- dynamic array append
- Adding a new element to the end of a list that can automatically grow in size.
Recall questions
- List the common complexity classes from fastest to slowest growth.
- Given a problem constraint of n <= 10^6, what is the maximum acceptable time complexity and why?
- Name one algorithm that runs in each of these classes: O(1), O(log n), O(n), O(n log n), O(n^2).
Understanding checks
You need to sort 10 million integers. You have two options: an O(n^2) insertion sort and an O(n log n) merge sort. At roughly 10^8 simple operations per second, estimate the wall-clock time for each and decide.
Insertion sort: (10^7)^2 = 10^14 operations, roughly 10^6 seconds (about 11 days). Merge sort: 10^7 * 23 = 2.3 * 10^8 operations, roughly 2.3 seconds. Merge sort is the only feasible option.
This drives home that the gap between O(n^2) and O(n log n) is not a minor optimization — it is the difference between seconds and days. The complexity class is the single most important factor at scale.
An algorithm correctly solves a problem for n = 100 in under a second, but times out when n = 10,000. Without seeing the code, what complexity class do you suspect and why?
Most likely O(n^2) or O(n^3). At n = 100, n^2 = 10,000 operations (fast). At n = 10,000, n^2 = 10^8 (borderline) and n^3 = 10^12 (certainly times out). The 100x increase in input causing a timeout strongly suggests a polynomial of degree 2 or higher.
This is the practical skill of reverse-engineering complexity from observed behavior — a direct application of knowing the growth rates of each class.
Practice tasks
Map constraints to the tightest feasible complexity
For each constraint below, determine the maximum complexity class that will run within approximately 10^8 operations and suggest an algorithm pattern that achieves it: (a) n <= 10, (b) n <= 1000, (c) n <= 10^5, (d) n <= 10^7.
Continue learning
Previous: Big-O Notation
Next: Logarithms & Powers of Two
Next: Amortized Analysis