Reading Complexity Classes

The notations have been defined; this lesson makes concrete the growth classes they represent. The goal is to know numerically what a cost expression means on sight: whether an $O(n^2)$ algorithm can work with a million elements is a matter of calculation, not guesswork.

Classes

The commonly encountered classes, from slowest to fastest growing:

Class	Name	Typical example
$O(1)$	Constant	Array element access, hash table lookup
$O(\log n)$	Logarithmic	Binary search, search in a balanced tree
$O(n)$	Linear	Scanning an array, finding the largest
$O(n \log n)$	Linearithmic	Efficient sorting algorithms
$O(n^2)$	Quadratic	Two nested loops, elementary sorts
$O(n^3)$	Cubic	Three-dimensional nested loop, naive matrix multiplication
$O(2^n)$	Exponential	Trying every subset
$O(n!)$	Factorial	Trying every ordering

There are also classes in between — such as $O(\sqrt{n})$, $O(n \log \log n)$, $O(n^{2.37})$ — but the list above covers most of practice.

Numerical Comparison

The difference between classes becomes visible once a few numbers are written down.

import math

def operation_count(n: int) -> dict[str, float]:
    return {
        "log n": math.log2(n),
        "n": n,
        "n log n": n * math.log2(n),
        "n²": n**2,
        "2ⁿ": 2**n if n <= 40 else float("inf"),
    }

for n in (10, 100, 1_000, 1_000_000):
    d = operation_count(n)
    print(n, {k: f"{v:.3g}" for k, v in d.items()})

# 10      {'log n': '3.32', 'n': '10',  'n log n': '33.2', 'n²': '100', '2ⁿ': '1.02e+03'}
# 100     {'log n': '6.64', 'n': '100', 'n log n': '664',  'n²': '1e+04', '2ⁿ': 'inf'}
# 1000    {'log n': '9.97', 'n': '1e+03', 'n log n': '9.97e+03', 'n²': '1e+06', '2ⁿ': 'inf'}
# 1000000 {'log n': '19.9', 'n': '1e+06', 'n log n': '1.99e+07', 'n²': '1e+12', '2ⁿ': 'inf'}

At a million elements, a logarithmic algorithm takes twenty steps; a quadratic algorithm takes a trillion. The difference is not “a bit slower” — it is the difference between a problem being solvable and not.

That the exponential column is not computed above forty is not a convenience but a necessity: the value $2^{100}$ is on the order of the number of atoms in the universe.

Scaling Behavior

The most useful question in practice is: how does cost change if the input doubles?

Class	Cost when input is $2\times$	When input is $10\times$
$O(1)$	Unchanged	Unchanged
$O(\log n)$	Increases by a constant amount	Increases by a constant amount
$O(n)$	$2\times$	$10\times$
$O(n \log n)$	A little more than $2\times$	A little more than $10\times$
$O(n^2)$	$4\times$	$100\times$
$O(n^3)$	$8\times$	$1000\times$
$O(2^n)$	Gets squared	Meaningless

This table makes it possible to estimate without measuring. A quadratic operation that takes two seconds with a thousand records takes two hundred seconds with ten thousand. If the same job is done with a linearithmic algorithm, tenfold data brings roughly a thirteenfold increase.

It is also used in reverse: an algorithm’s class can be estimated by looking at how measured times change with input. If time quadruples when input doubles, there is quadratic behavior in the code.

Sublinear Classes

Classes like $O(\log n)$ and $O(\sqrt{n})$ produce a result without reading all of the input. This is possible only if the data is already organized: binary search assumes sortedness, a hash table assumes a table already built.

For this reason, sublinear costs usually come together with a preprocessing cost. If an array is going to be sorted and then searched a thousand times, the $O(n \log n)$ sorting cost is divided across the thousand searches and pays for itself many times over. Sorting for a single search, on the other hand, makes no sense.

This is the decision criterion: once the preprocessing cost is divided by the number of queries, is there still a gain?

Why $n \log n$ Appears Often

This class appears often for two reasons.

The first is that it is the natural consequence of the divide-and-conquer structure: the problem is split in two at every step ($\log n$ depth), and all elements are processed at every level ($n$ work). Merge sort is the canonical example of this.

The second is that it is the lower bound for comparison-based sorting: no comparison-based algorithm can be faster than this. This result will be proved in the searching and sorting topic.

Exponential Classes and Combinatorial Explosion

Exponential and factorial classes arise from solutions of the form “try every possibility”:

• All subsets of $n$ elements: $2^n$ of them.
• All orderings of $n$ elements: $n!$ of them.

import math
for n in (10, 20, 30, 50):
    print(n, f"2^n = {2**n:.3g}", f"n! = {math.factorial(n):.3g}")

# 10 2^n = 1.02e+03 n! = 3.63e+06
# 20 2^n = 1.05e+06 n! = 2.43e+18
# 30 2^n = 1.07e+09 n! = 2.65e+32
# 50 2^n = 1.13e+15 n! = 3.04e+64

With thirty elements, the number of subsets exceeds a billion; with twenty elements, the number of orderings reaches two quintillion. This shows why brute-force solutions can be used only on very small inputs.

In such problems, three paths are followed: keeping the input small, narrowing the search space with intelligent pruning (backtracking from the Programming Fundamentals course), or giving up on an exact solution and producing an approximate result. The theoretical classification of these problems belongs to the Theory of Computation course.

When Constants Matter

Asymptotic notation eliminates constants, but constants exist in the real world and dominate at small inputs.

When an algorithm costing $100n$ is compared to one costing $n^2$, the second is faster for $n < 100$. The crossover point is determined by the ratio of the constants.

The practical consequence is seen in library implementations: sorting algorithms switch to insertion sort on small subarrays, because at those sizes the simple algorithm’s small constant wins out. This kind of hybrid approach shows where asymptotic analysis ends and measurement begins.

Summary

• Classes are ordered from constant and logarithmic to exponential and factorial; the differences between them are of order at large inputs.
• How cost changes when input doubles is the practical way to recognize a class.
• Sublinear classes require data that is already organized; preprocessing cost is evaluated by dividing it across the number of queries.
• $n \log n$ is both the natural consequence of the divide-and-conquer structure and the lower bound for comparison-based sorting.
• Exponential and factorial classes arise from brute-force solutions and are practical only for very small inputs.
• Constants dominate at small inputs; libraries therefore use hybrid approaches.

Next Step

The classes have been recognized; next comes determining which class a piece of code belongs to by looking at it. The next lesson will build, step by step, the methods for computing the cost of loops, recursion, and amortized operations.