Growth rates and what fits in a time limit

Asymptotic notation says how the cost of an algorithm grows with the input, but a program is judged in seconds: an online judge stops it after one or two, and a user gives up after a few. This lesson joins the two views. You will rank the common growth rates, turn a time limit into a budget of steps, see how that budget changes from one runtime to another, and read a problem’s limits to decide how fast the algorithm has to be before you write any code.

The ladder of growth rates

These are the growth rates you will meet most often, from the one that grows most slowly to the one that grows fastest, each with a typical source of that cost:

• O(1), constant: reading a list element by its index, or looking a key up in a hash table (on average).
• O(log n), logarithmic: binary search, which halves the part still to search at every step.
• O(√n): testing whether n is prime by trying divisors up to √n.
• O(n), linear: one pass over the input, such as finding the largest element.
• O(n log n): sorting by comparing elements, as Python’s sorted() does.
• O(n²), quadratic: looking at every pair of elements.
• O(n³), cubic: every triple of elements, or the simple way of multiplying two n × n matrices.
• O(2ⁿ), exponential: trying every subset of n items.
• O(n!), factorial: trying every ordering of n items.

Each rate stands for a count of steps, so the clearest way to compare them is to work the counts out. This program prints the step count of each rate for four input sizes:

import math

SIZES = [10, 100, 1_000, 1_000_000]


def shown(x):
    """A step count as it is usually written: plain while it is short, then in e-notation (1.0e6 = 1.0 x 10^6)."""
    if x >= 10_000:
        exponent = len(str(int(x))) - 1
        return f"{x / 10**exponent:.1f}e{exponent}"
    if x == int(x) or x >= 100:
        return f"{round(x):,}"
    return f"{x:.1f}"


def two_to_the(n):
    if n <= 1_000:
        return shown(2**n)
    return f"{math.floor(n * math.log10(2)) + 1:,} digits"


def factorial(n):
    if n <= 1_000:
        return shown(math.factorial(n))
    return f"{math.floor(math.lgamma(n + 1) / math.log(10)) + 1:,} digits"


RATES = [
    ("1", lambda n: shown(1)),
    ("log2 n", lambda n: shown(math.log2(n))),
    ("sqrt n", lambda n: shown(math.sqrt(n))),
    ("n", lambda n: shown(n)),
    ("n log2 n", lambda n: shown(n * math.log2(n))),
    ("n^2", lambda n: shown(n**2)),
    ("n^3", lambda n: shown(n**3)),
    ("2^n", two_to_the),
    ("n!", factorial),
]

widths = [9, 9, 10, 17]
print(f"{'rate':<9}" + "".join(f"{f'n={n:,}':>{w}}" for n, w in zip(SIZES, widths)))
for name, steps in RATES:
    print(f"{name:<9}" + "".join(f"{steps(n):>{w}}" for n, w in zip(SIZES, widths)))

rate          n=10    n=100   n=1,000      n=1,000,000
1                1        1         1                1
log2 n         3.3      6.6      10.0             19.9
sqrt n         3.2       10      31.6            1,000
n               10      100     1,000            1.0e6
n log2 n      33.2      664     9,966            2.0e7
n^2            100    1.0e4     1.0e6           1.0e12
n^3          1,000    1.0e6     1.0e9           1.0e18
2^n          1,024   1.3e30   1.1e301   301,030 digits
n!           3.6e6  9.3e157  4.0e2567 5,565,709 digits

The output writes large numbers in e-notation: 2.0e7 is 2.0 × 10⁷, twenty million. Three things stand out:

• Up to n log n, a million items is easy. Even n log₂ n is only about twenty million steps for n = 1,000,000.
• Quadratic and cubic costs explode at large n. A million items need 10¹² steps at O(n²): almost three hours at 10⁸ steps per second.
• Exponential and factorial costs explode at small n. 2¹⁰⁰ is already a 31-digit number, and 2ⁿ for a million items is a number with 301,030 digits. Doubling n squares 2ⁿ, because 2²ⁿ = (2ⁿ)², so no faster computer rescues an exponential algorithm.

Big-O hides constant factors and smaller terms, so at small n a costlier rate can still be faster in practice. The ladder tells you which algorithm wins once inputs are large, and what follows tells you where “large” starts.

How many steps fit in a second

A simple step here is one turn of a tight loop that does a little arithmetic, a comparison or an index lookup. A time limit becomes a budget of steps: the number of simple steps the runtime manages per second, times the number of seconds. Given a budget, you can work out the largest input each growth rate can handle. This program does it for budgets from a million to a billion steps:

import math

RATES = [
    ("n", lambda n: n),
    ("n log2 n", lambda n: n * math.log2(n)),
    ("n^2", lambda n: n**2),
    ("n^3", lambda n: n**3),
    ("2^n", lambda n: 2**n),
    ("n!", math.factorial),
]
BUDGETS = [10**6, 10**7, 10**8, 10**9]


def largest_n(steps, budget):
    """The largest n with steps(n) <= budget, for a step count that grows with n."""
    high = 1
    while steps(high * 2) <= budget:  # double until we overshoot ...
        high *= 2
    low, high = high, high * 2  # ... then binary search between the last two guesses
    while high - low > 1:
        middle = (low + high) // 2
        if steps(middle) <= budget:
            low = middle
        else:
            high = middle
    return low


print(f"{'rate':<9}" + "".join(f"{f'1e{len(str(b)) - 1} steps':>14}" for b in BUDGETS))
for name, steps in RATES:
    print(f"{name:<9}" + "".join(f"{largest_n(steps, b):>14,}" for b in BUDGETS))

rate          1e6 steps     1e7 steps     1e8 steps     1e9 steps
n             1,000,000    10,000,000   100,000,000 1,000,000,000
n log2 n         62,746       526,172     4,523,071    39,620,077
n^2               1,000         3,162        10,000        31,622
n^3                 100           215           464         1,000
2^n                  19            23            26            29
n!                    9            10            11            12

largest_n doubles its guess until the step count overshoots the budget, then binary-searches between the last two guesses, a technique that the binary search module of this track comes back to. The diagram puts the 10⁸ column next to the ladder:

Read across a row and the effect of a faster computer appears: ten times the budget lets an O(n) algorithm handle ten times the input, an O(n²) one about three times (√10 ≈ 3.2), an O(n³) one a little over twice, and O(2ⁿ) only three or four more items.

The same loop in four runtimes

How many simple steps run in a second depends a great deal on the runtime, not only on the computer. The next two programs run the same loop, a million additions, and report the best of nine tries. First Python:

import sys
import time

STEPS = 1_000_000


def count_up(steps):
    total = 0
    for i in range(steps):
        total += i
    return total


# Nine short tries, keeping the fastest: a slower try lost time to other programs.
best = float("inf")
for attempt in range(9):
    start = time.perf_counter()
    total = count_up(STEPS)
    best = min(best, time.perf_counter() - start)

assert total == STEPS * (STEPS - 1) // 2
rate = STEPS / best
print(f"Python {sys.version.split()[0]} on {sys.platform}")
print(f"{STEPS:,} loop steps: {best * 1000:.1f} ms at best")
print(f"about {float(f'{rate:.2g}'):,.0f} simple steps per second")

Python 3.14.8 on darwin
1,000,000 loop steps: 44.4 ms at best
about 23,000,000 simple steps per second

Then JavaScript:

// performance.now() where it exists (Node.js, browsers); QuickJS has only Date.now(), in whole milliseconds.
const now = typeof performance === 'object' ? () => performance.now() : () => Date.now();
const STEPS = 1_000_000;

function countUp(steps) {
  let total = 0;
  for (let i = 0; i < steps; i++) total += i;
  return total;
}

const withCommas = (n) => String(Math.round(n)).replace(/\B(?=(\d{3})+(?!\d))/g, ',');

// Nine short tries, keeping the fastest: a slower try lost time to other programs (or ran before the JIT).
let best = Infinity;
let total = 0;
for (let attempt = 0; attempt < 9; attempt++) {
  const start = now();
  total = countUp(STEPS);
  best = Math.min(best, now() - start);
}

if (total !== (STEPS * (STEPS - 1)) / 2) throw new Error(`wrong total: ${total}`);
const engine = typeof process === 'object' ? `Node.js ${process.versions.node} (V8 ${process.versions.v8})` : 'an engine without Node.js';
const rate = STEPS / (Math.max(best, 0.001) / 1000);
console.log(`JavaScript in ${engine}`);
console.log(`${withCommas(STEPS)} loop steps: ${best.toFixed(1)} ms at best`);
console.log(`about ${withCommas(Number(rate.toPrecision(2)))} simple steps per second`);

JavaScript in Node.js 24.21.0 (V8 13.6.233.17-node.53)
1,000,000 loop steps: 1.3 ms at best
about 790,000,000 simple steps per second

The outputs shown above were recorded with CPython and Node.js on one computer; the Run buttons measure the two browser runtimes on yours. The four rates for the same million additions are far apart, and each program checks the total, so none of them skips work:

• CPython compiles Python to bytecode and interprets it: a few tens of millions of steps per second.
• V8, the engine inside Node.js and Chrome, compiled the loop to machine code with its just-in-time (JIT) compiler: close to a billion steps per second.
• Pyodide, the same CPython compiled to WebAssembly, and QuickJS, a JavaScript interpreter compiled to WebAssembly, manage millions of steps per second: a few times fewer than CPython and roughly a hundred times fewer than V8.

Code that a runtime runs in C, such as Python’s sorted(), sum() and dictionary operations, does not pay the interpreter’s cost for every element, so in Python a built-in is often faster than a hand-written loop of the same growth rate. The documented costs of Python’s built-in types are listed on the page of the Python documentation named in this lesson’s references.

From limits to a target complexity

A problem statement tells you most of what you need: the largest input, the time limit, and often more. Before choosing an approach, read:

• The largest n, and whether there are several inputs. “The sum of n over all test cases is at most 200,000” means the total is limited, not each test, so an O(n log n) algorithm per test is fine.
• The time limit, multiplied by the steps per second of the language you write in.
• The size of the values. Values up to 10⁹ summed over 200,000 items overflow a 32-bit integer in Java or C++; Python’s integers grow as needed.
• The number of queries. 100,000 queries on an array of 100,000 items cost 10¹⁰ steps if each query scans the array, so each query has to be O(log n) or O(1) after some preparation.

Then compare each idea’s step count with the budget. This worksheet does it for four made-up problems and two budgets, 10⁸ steps per second for compiled code and 10⁷ for CPython; press Edit to try your own limits:

import math

COMPILED = 10**8  # simple steps per second in compiled code or a JIT engine (a planning figure)
CPYTHON = 10**7  # the same for CPython, leaving room for steps that do more than one addition

COSTS = {
    "log2 n": lambda n: math.log2(n),
    "n": lambda n: n,
    "n log2 n": lambda n: n * math.log2(n),
    "n^2": lambda n: n**2,
    "n^3": lambda n: n**3,
    "2^n * n": lambda n: 2**n * n,
}

# (what the problem asks, the largest n it allows, its time limit in seconds, the candidates you thought of)
PROBLEMS = [
    ("two marks that add up to k", 200_000, 1, ["n^2", "n log2 n"]),
    ("the best team out of n people", 20, 1, ["2^n * n"]),
    ("travel times between all pairs of n towns", 400, 2, ["n^3"]),
    ("the number of binary digits of n", 10**18, 1, ["n", "log2 n"]),
]


def shown(x):
    if x < 10_000:
        return f"{round(x):,}"
    exponent = len(str(int(x))) - 1
    return f"{x / 10**exponent:.1f}e{exponent}"


for task, n, seconds, candidates in PROBLEMS:
    print(f"{task}: n <= {n:,}" if n < 10**7 else f"{task}: n <= {shown(n)}", f"in {seconds} s")
    for name in candidates:
        steps = COSTS[name](n)
        if steps <= CPYTHON * seconds:
            verdict = "fits, even in CPython"
        elif steps <= COMPILED * seconds:
            verdict = "fits in compiled code, too slow for CPython"
        else:
            verdict = "too slow"
        print(f"  {name:<9}{shown(steps):>8} steps  {verdict}")

two marks that add up to k: n <= 200,000 in 1 s
  n^2        4.0e10 steps  too slow
  n log2 n    3.5e6 steps  fits, even in CPython
the best team out of n people: n <= 20 in 1 s
  2^n * n     2.1e7 steps  fits in compiled code, too slow for CPython
travel times between all pairs of n towns: n <= 400 in 2 s
  n^3         6.4e7 steps  fits in compiled code, too slow for CPython
the number of binary digits of n: n <= 1.0e18 in 1 s
  n          1.0e18 steps  too slow
  log2 n         60 steps  fits, even in CPython

Together with the table of largest inputs, the worksheet gives the usual reading of the most common limits. With n up to about 10 or 11, even n! fits; up to about 20 to 25, 2ⁿ fits; a few hundred allows n³; a few thousand allows n²; and from about 100,000 upwards you need n log n or better. It also shows that the language matters near the edges: the team problem and the towns problem fit in compiled code but would need a smarter algorithm, or a faster language, in CPython.

Key takeaways

• From slowest-growing to fastest: 1, log n, √n, n, n log n, n², n³, 2ⁿ, n!. Exponential and factorial costs explode while n is still small; quadratic and cubic costs explode as n reaches thousands and millions.
• A time limit is a budget of steps: steps per second times seconds. Plan with about 10⁸ steps per second for compiled code and JIT engines and about 10⁷ for CPython.
• For a budget of 10⁸ steps, the largest inputs are about 11 for n!, 26 for 2ⁿ, 464 for n³, 10,000 for n² and 4.5 million for n log n.
• Read the largest n, the time limit, the size of the values and the number of queries, then choose the costliest approach whose step count still fits.