---
title: 'Reading Complexity Classes'
source: 'https://academia.sh/en/courses/algorithms/complexity-classes'
course: Algorithms
language: en
updated: '2026-08-17T18:07:32+00:00'
license: 'CC BY-SA 4.0'
---

# Reading Complexity Classes

Constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial growth; scaling behavior and practical limits.

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.

```python
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.

```python
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.