Complexity and Big-O

The measuring stick for everything else in this guide. This file covers the formal machinery (O/Theta/Omega, amortized analysis, recurrences) but spends most of its space on the two things that actually get you through an interview: mechanically deriving a bound from code you are looking at, and knowing the real complexity of the language built-ins you reach for by reflex. Every number in the benchmark tables was measured on the machine this guide was written on — CPython 3.11.15 and Node 22.22.2 / V8 12.4 on a small 2-core cloud container. Treat the absolute values as indicative and the shapes (the growth exponents) as the point.

Table of contents

• 1. Why asymptotics, and where they lie
• 2. Formal definitions
• 3. The growth hierarchy and what n you can afford
• 4. Space complexity and the recursion stack
• 5. Amortized analysis
• 6. Recurrences and the Master Theorem
• 7. Reading complexity off code, mechanically
• 8. Complexity of the built-ins
• 9. The measured traps
• 10. Expected and probabilistic complexity
• 11. Lower bounds and “can you do better?”
• 12. Talking about complexity in the interview
• 13. Interview follow-ups

1. Why asymptotics, and where they lie

The model is the RAM machine: unit-cost arithmetic on machine words, unit-cost indexed memory access, and we count operations as a function of input size. That model buys us the ability to compare algorithms without a benchmark, and it costs us three things you should be ready to name when an interviewer pushes:

1. Memory is not unit-cost. L1 is roughly 1 ns, main memory roughly 100 ns. Two Theta(n^2) loops over the same matrix differ by an order of magnitude depending on stride. Measured here, walking a flat array('q') of n*n with stride 1 versus stride n — identical operation count:

        n       stride 1       stride n   slowdown
      512         0.0142         0.0286      2.02x
     1024         0.0519         0.1521      2.93x
     2048         0.2173         0.7567      3.48x

   And in Node, on a Float64Array, where the JIT removes the interpreter overhead and exposes the memory system directly:

        n      MiB   stride 1 s   stride n s   slowdown
      512      2.0      0.00032      0.00087      2.75x
     1024      8.0      0.00133      0.00355      2.66x
     2048     32.0      0.00894      0.03523      3.94x
     4096    128.0      0.03491      0.21943      6.29x

   The slowdown grows with n because the working set outgrows each cache level in turn. This is why an array-backed structure beats a pointer-based one with the same asymptotics: same Theta(n) walk, 4x apart at n = 4,000,000.

           n    contiguous        chased   slowdown
     100,000        0.0060        0.0104      1.72x
   1,000,000        0.0471        0.1094      2.32x
   4,000,000        0.1932        0.7609      3.94x

2. Constants are the whole story at interview-sized n. O(log n) beats O(n) asymptotically, but where is the crossover? Measured, linear scan versus bisect on a sorted Python list:

        n   linear ns/query   bisect ns/query     winner
        2             145.9              61.9     bisect
        4             165.0             141.3     bisect
        8             426.7             165.7     bisect
       16             616.3             196.5     bisect
      512            6500.6             204.8     bisect

   Here bisect wins from n = 2, because it is C code and the Python loop is bytecode. Rewrite the linear scan in C (in on a list) and the crossover moves to a few dozen. The lesson is not “always binary search” — it is that the crossover is an empirical question about constants, and the asymptotics only tell you which side of it grows.

3. n is often small and bounded. Insertion sort beats quicksort below ~16 elements, which is exactly why every production sort (TimSort in V8 and CPython, introsort in C++) switches to it. Saying this out loud is a strong signal.

State the bound, then state the caveat. “It’s O(n log n), but the comparator dominates so in practice I’d care more about how expensive key() is” is a better answer than the bound alone.

2. Formal definitions

For functions f, g from the naturals to the non-negative reals:

Read = as “is in”. O is an upper bound, Omega a lower bound, Theta a tight bound.

Proving membership. To show 3n^2 + 5n + 7 = O(n^2): for n >= 1, 3n^2 + 5n + 7 <= 3n^2 + 5n^2 + 7n^2 = 15n^2, so c = 15, n0 = 1. To show it is not O(n): 3n^2/n = 3n grows without bound, so no constant c works.

The two misuses to avoid.

• “Worst case” is not the same as “upper bound”. O describes a function; “worst case” describes which input you chose. You can legitimately say “the best case is O(n)” — those are orthogonal axes. Sloppiness here is a common interview tell.
• O is an upper bound, so it is not tight by definition. Merge sort is O(n^100). True and useless. If you know the bound is tight, say Theta; most people say O and mean Theta, which is fine as long as you can answer “is that tight?”

Useful algebra.

• O(f) + O(g) = O(max(f, g)); constants and lower-order terms vanish.
• O(f)·O(g) = O(f·g) — nesting multiplies.
• log_a n = Theta(log_b n), so the base of a logarithm is a constant factor and is dropped.
• n^k = o(c^n) for any k and c > 1; log^k n = o(n^e) for any e > 0. Polynomials beat logs, exponentials beat polynomials.
• Sum of the first n integers is Theta(n^2); the harmonic sum H(n) = Theta(log n).
• Stirling: log(n!) = Theta(n log n). This is the comparison-sort lower bound in disguise.

3. The growth hierarchy and what n you can afford

graph LR
  A["O(1)<br/>hash lookup"] --> B["O(log n)<br/>binary search"]
  B --> C["O(sqrt n)<br/>trial division"]
  C --> D["O(n)<br/>single scan"]
  D --> E["O(n log n)<br/>comparison sort"]
  E --> F["O(n^2)<br/>nested loops"]
  F --> G["O(n^3)<br/>Floyd-Warshall"]
  G --> H["O(2^n)<br/>subsets"]
  H --> I["O(n!)<br/>permutations"]

3.1 What actually fits in one second

Measured by calibrating each shape on real code and extrapolating to a 1-second budget.

CPython 3.11.15 (pure-Python loops):

class                |      calib n | measured s |          max n in 1s
------------------------------------------------------------------------
O(log n)             |    1,048,576 |     0.2302 |             1.41e+26
O(sqrt n)            |  100,000,000 |     0.0013 |   56,049,500,102,307
O(n)                 |    3,000,000 |     0.1235 |           24,287,143
O(n log n) pure-py   |      200,000 |     0.5418 |              352,754
O(n log n) .sort()   |    1,000,000 |     0.3286 |            2,829,789
O(n^2)               |        2,000 |     0.1217 |                5,733
O(n^3)               |          250 |     0.3883 |                  342
O(2^n)               |           22 |     0.1833 |                   24
O(n!)                |           10 |     0.2487 |                   10

Node 22 / V8 (same shapes, JIT-compiled):

class                  |      calib n | measured s |          max n in 1s
--------------------------------------------------------------------------
O(log n)               |    1,048,576 |     0.0039 | effectively unbounded
O(sqrt n)              |  100,000,000 |     0.0002 |             3.97e+15
O(n)                   |   30,000,000 |     0.0367 |          818,045,450
O(n log n) hand-merge  |      500,000 |     0.3726 |            1,254,098
O(n log n) .sort()     |    2,000,000 |     1.7885 |            1,161,732
O(n^2)                 |       10,000 |     0.1552 |               25,387
O(n^3)                 |          700 |     0.5332 |                  863
O(2^n)                 |           25 |     0.0514 |                   29
O(n!)                  |           11 |     0.4593 |                   11

Rules of thumb worth memorizing, derived from the above:

• Node’s tight numeric loop is ~30x faster than CPython’s. 8e8 vs 2.4e7 simple operations per second. That gap is the single biggest practical difference between the two languages in a coding round, and it is why the same O(n^2) solution passes in JS and TLEs in Python.
• Pushing work into C is worth an order of magnitude in Python. list.sort() handles 2.8e6 elements per second while a hand-written pure-Python merge sort handles 3.5e5 — 8x. Same asymptotics. In Node the JIT closes that gap entirely (hand-merge actually beats .sort() here because .sort() pays a comparator call per comparison).
• Competitive-programming heuristic: with a 1-second limit assume ~1e8 simple ops in a compiled language, ~1e7 in Node, ~1e6–1e7 in Python. From the constraint you can read off the intended complexity: n <= 20 means exponential/bitmask; n <= 500 means O(n^3); n <= 5,000 means O(n^2); n <= 1e5 means O(n log n); n <= 1e7 means O(n) and you should avoid allocating.

4. Space complexity and the recursion stack

Auxiliary space is what your algorithm allocates beyond the input; total space includes the input. “In-place” conventionally means O(1) auxiliary — which is why in-place quicksort is still O(log n) space (the recursion stack) and why heapsort is the genuinely O(1) comparison sort.

Common auxiliary costs:

4.1 Measured recursion limits

Python guards depth with a counter, not the real stack:

sys.getrecursionlimit() default = 1000
frames reached before RecursionError (default limit) = 998
limit=2,000,000 thread stack=  1 MiB -> depth 1999996 (RecursionError)
limit=2,000,000 thread stack=  8 MiB -> depth 1999996 (RecursionError)

Two things to notice. First, the default ceiling is ~1000 frames, so any recursion over an input of size 1e5 needs to be iterative — a linked list of 100,000 nodes will blow up a recursive reversal. Second, since CPython 3.11 pure-Python frames live on a heap-allocated chunked stack, so raising sys.setrecursionlimit no longer segfaults for simple Python recursion (the thread stack size stopped mattering — all three thread-stack sizes reached the same depth). Recursion that crosses back into C (__repr__, sorted with a recursive key, copy.deepcopy) still uses the C stack and there threading.stack_size() plus a worker thread is the real fix.

Node guards with the actual stack, so frame size matters:

stack-size flag: (default)
no-arg frame        : 12554
4-arg frame         :  6974
8-local frame       :  6974

Roughly 12,500 trivial frames, halving as you add arguments or locals. node --stack-size=N (in KB) raises it, at the risk of a hard segfault instead of a catchable RangeError. There are no proper tail calls in V8, so the fix is always an explicit stack or a loop.

The interview-relevant conclusion: if the input can exceed ~1000 (Python) or ~10,000 (Node), convert recursion to iteration. Both languages give you the same three tools — an explicit stack, an explicit work queue, or bottom-up DP instead of top-down memoization.

5. Amortized analysis

Amortized cost is the average cost per operation over a worst-case sequence. It is not the average case (which averages over inputs, using probability) and it is not the best case. A sequence of n pushes on a dynamic array costs O(n) total, so O(1) amortized, even though one individual push costs O(n).

Three methods:

5.1 Dynamic array growth

Aggregate. With a doubling policy starting at capacity 1, resizes happen at sizes 1, 2, 4, …, and copy that many elements. Total copying for n appends is 1 + 2 + 4 + … + 2^(log n) < 2n = O(n), so O(1) amortized.

Potential. Let Phi = 2·size - capacity. A non-resizing append costs 1 and raises Phi by 2, so amortized 3. A resizing append (size = capacity = k) costs k+1 to copy and Phi goes from k to 2(k+1) - 2k = 2, a drop of k-2, so amortized 3. Constant either way.

Growth factor matters. With a factor of g, the total copy cost is n·g/(g-1). Doubling gives 2n; 1.5x gives 3n; and CPython’s ~1.125x gives 9n — nine times more copying, in exchange for far less wasted memory and a much better chance of extending the allocation in place. Measured CPython list growth (sys.getsizeof as we append):

     len  getsizeof   capacity   event
       1         88          4   grow
       5        120          8   grow
       9        184         16   grow
      17        248         24   grow
      25        312         32   grow
      33        376         40   grow
      41        472         52   grow
      53        568         64   grow

total reallocations while appending 1,000,000 items: 86
capacity sequence (first 24): [4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128, 148, 172, 200, 232, ...]
growth ratio: first=2.000 median=1.12569 last=1.12501
asymptotic factor approaches 1.125006  (CPython: new = n + n>>3 + 6, rounded)

86 reallocations for a million appends, and the ratio converges on 9/8. The formula in CPython’s list_resize is new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3 — grow by an eighth, add a fudge factor, round to a multiple of 4. sys.getsizeof([]) == 56 (header only) and each slot is one 8-byte pointer, which is how you read capacity out of getsizeof.

V8 grows JS arrays by roughly 1.5x plus a constant (new = old + old/2 + 16), and shrinks when the array becomes less than half full.

5.2 The two-stack queue

Keep inbox and outbox. enqueue pushes onto inbox. dequeue pops outbox, and when outbox is empty, pours all of inbox into it.

class Queue:
    def __init__(self): self._in, self._out = [], []
    def enqueue(self, x): self._in.append(x)
    def dequeue(self):
        if not self._out:
            while self._in: self._out.append(self._in.pop())
        if not self._out: raise IndexError("empty")
        return self._out.pop()

A single dequeue can cost O(n), but each element is moved from inbox to outbox exactly once in its lifetime. Accounting: charge 3 credits at enqueue (one to push, one to move, one to pop later); the balance is never negative, so every operation is O(1) amortized.

Say the caveat too: amortized O(1) is not the same as worst-case O(1), and for a real-time system (a frame budget, an audio callback) the O(n) spike is a bug. That is what a fixed-capacity ring buffer or an incremental-rehash hash table is for.

5.3 Other classic amortized results

6. Recurrences and the Master Theorem

6.1 The three techniques

Substitution — guess and prove by induction. Guess T(n) <= c·n·log n for merge sort: T(n) = 2T(n/2) + n <= 2c(n/2)log(n/2) + n = cn log n - cn + n <= cn log n for c >= 1.

Recursion tree — draw the levels, sum the work per level, multiply by the number of levels. For T(n) = 2T(n/2) + n: each level does n work, there are log n levels, total Theta(n log n). For T(n) = 2T(n/2) + 1: level i does 2^i work, the last level dominates with n leaves, total Theta(n).

Master Theorem — for T(n) = a·T(n/b) + f(n) with a >= 1, b > 1, let c_crit = log_b(a):

The regularity condition in case 3 is what people forget. It fails for pathological f like n^2·sin^2(n); when it fails, use Akra–Bazzi.

6.2 Worked examples

Quickselect’s average case needs a different argument: E[T(n)] = T(3n/4) + O(n) in expectation over random pivots (the pivot lands in the middle half with probability 1/2), which telescopes to O(n) — the same geometric series as the case-3 row above. Median-of-medians makes that worst-case O(n) at the cost of a large constant.

Akra–Bazzi, in one line, for unequal splits T(n) = sum(a_i·T(b_i·n)) + f(n): find p with sum(a_i·b_i^p) = 1, then T(n) = Theta(n^p·(1 + integral of f(u)/u^(p+1) du)). You will almost never need it, but naming it when a recurrence has unequal splits (like T(n) = T(n/3) + T(2n/3) + n, which is Theta(n log n)) is a good signal.

7. Reading complexity off code, mechanically

7.1 Loops

for i in range(n):            # n
    for j in range(n):        # x n
        work()                # = Theta(n^2)

for i in range(n):            # dependent bounds: sum_{i} i = n(n-1)/2
    for j in range(i):
        work()                # = Theta(n^2), same class, half the constant

i = 1
while i < n:                  # multiplicative update
    i *= 2                    # = Theta(log n)

for i in range(n):            # harmonic sum: n/1 + n/2 + n/3 + ... = n·H(n)
    for j in range(i, n, i+1):
        work()                # = Theta(n log n)   <- this is the sieve pattern

The sieve of Eratosthenes is the famous case: the inner loop runs n/p times for each prime p, and sum over primes of n/p = Theta(n log log n) by Mertens’ theorem. Interviewers accept “n log log n, essentially linear”.

7.2 The nested loop that is not quadratic

This is the single most common place people misjudge a bound. Two rules:

Rule 1 — count total inner iterations, not the nesting depth.

# Two pointers: the inner while never resets. Each pointer advances at most n times.
l = 0
for r in range(n):
    while l < r and bad(l, r):
        l += 1                     # total work across ALL iterations <= n
# Theta(n), despite the nested while.

# Monotonic stack: each element is pushed once and popped at most once.
st = []
for x in arr:
    while st and st[-1] < x:
        st.pop()                   # total pops <= n
    st.append(x)
# Theta(n).

Rule 2 — if the inner loop’s bound is reset each time, it multiplies.

for r in range(n):
    l = 0                          # reset! now it really is quadratic
    while l < r: l += 1
# Theta(n^2).

The question to ask yourself is always: what is the total number of times this line executes over the whole run? Not how deep is it nested?

7.3 Recursion

Count nodes in the recursion tree times work per node.

def fib(n):                    # branching factor 2, depth n
    return n if n < 2 else fib(n-1) + fib(n-2)
# Theta(phi^n) ~ Theta(1.618^n), commonly stated as O(2^n).

def fib_memo(n, memo={}):      # each distinct n computed once
    ...
# Theta(n) time, Theta(n) space.

def subsets(arr, i=0, cur=[]):        # 2^n leaves, and O(n) to copy each
    ...
# Theta(n·2^n) time. The copy matters: people say 2^n and lose the n.

def permutations(arr): ...            # n! leaves, O(n) per leaf -> Theta(n·n!)

For a DP, the bound is almost always (number of states) x (work per state). Say it that way and you will never miscount: “the state is (index, remaining capacity), so O(n·W) states, O(1) transition, therefore O(n·W) time and O(W) space with the rolling array.”

7.4 Hidden linear costs

The most common source of an accidental extra factor of n:

a[1:]              # copies n-1 pointers    -> O(n)
s[i:j]             # copies characters      -> O(j-i)
list(x)            # O(n)
x in some_list     # O(n)
arr.insert(0, v)   # O(n) memmove
arr.pop(0)         # O(n) memmove
max(a)             # O(n) -- and O(n^2) when it is inside a loop
len(list(gen))     # consumes the generator, O(n), and the generator is now exhausted

[...arr]           // O(n)
arr.shift()        // O(n)
arr.unshift(v)     // O(n)
arr.splice(i,1)    // O(n)
arr.concat(b)      // O(n+m)
str.slice(i)       // O(1) in V8 (SlicedString) but flattening later is O(n)
Object.keys(o)     // O(n)

Measured, tail slicing inside a loop — 1000 slices of a list of n:

### 1000 tail slices a[i:] of a list of n   [each slice copies O(n) pointers]
         n      seconds        ns/op   t(2n)/t(n)   exponent
   100,000     0.135801     135801.1
   200,000     0.312493     312493.4         2.30       1.20
   400,000     0.907807     907806.9         2.91       1.54
   800,000     2.837960    2837960.0         3.13       1.64

The classic bug this creates is a “recursive quicksort” written with slicing, which is O(n log n) comparisons but O(n log n) copying on top, and a “sliding window” that re-slices instead of moving indices, which is O(n^2).

8. Complexity of the built-ins

8.1 JavaScript / TypeScript

8.2 Python

Verified against the Python wiki TimeComplexity page.

9. The measured traps

Every table below is real output. The “exponent” column is log2(t(2n)/t(n)) — the empirical growth exponent, so 1.0 means linear and 2.0 means quadratic. This is the single most useful debugging technique in this file: double n and see what the time does.

9.1 list.insert(0, x) vs deque.appendleft

### list.insert(0, x), n times                    ### deque.appendleft(x), n times
         n      seconds   ns/op   exponent                 n      seconds   ns/op   exponent
     4,000     0.002616   653.9                      100,000     0.002883    28.8
     8,000     0.010210  1276.2       1.96            200,000     0.005779    28.9      1.00
    16,000     0.041631  2601.9       2.03            400,000     0.012648    31.6      1.13
    32,000     0.163582  5112.0       1.97            800,000     0.028289    35.4      1.16

Quadratic versus linear, and at n = 32,000 the per-operation cost is already 5.1 microseconds versus 35 nanoseconds — 145x. Same story for list.pop(0) (exponent ~2.0, 46 microseconds per op at 32,000) versus deque.popleft (exponent ~1.1, 38 ns).

If you write a BFS with queue.pop(0) on a graph with 1e5 nodes, you have written an O(V^2) BFS. This is the most common performance bug in Python interview code.

9.2 in list vs in set vs in dict

### `x in list` (200,000 probes)            ### `x in set` (200,000 probes)
     n      ns/probe   exponent                  n      ns/probe   exponent
   500        1410.5                           500          42.6
 1,000        2556.0       0.86              1,000          42.8       0.01
 2,000        5182.0       1.02              2,000          43.2       0.01
 4,000       10911.8       1.07              4,000          43.8       0.02

Exponent 1.0 versus 0.0 — the definition of O(n) versus O(1). At n = 4,000 the set is 250x faster, and the gap grows without bound. dict measures identically to set (49 ns, exponent 0).

The interview move: any time you see a membership test inside a loop, hoist the collection into a set (or a JS Set). That single change is what turns most accidental O(n^2) solutions into O(n).

9.3 String building in Python, and the subtlety everyone gets wrong

### s += 'x' (plain local)  [CPython in-place resize fires -> LINEAR]
         n      seconds        ns/op   exponent
   100,000     0.004188         41.9
   200,000     0.008397         42.0       1.00
   400,000     0.016957         42.4       1.01
   800,000     0.033730         42.2       0.99

### s += 'x' (one extra reference alive)  [in-place resize BLOCKED -> QUADRATIC]
    25,000     0.004784        191.4
    50,000     0.028328        566.6       2.57
   100,000     0.158448       1584.5       2.48
   200,000     0.760010       3800.0       2.26

### obj.s += 'x' (attribute, not a local)  [STORE_ATTR -> QUADRATIC]
    16,000     0.002362        147.6       1.30
    32,000     0.010054        314.2       2.09

### ''.join(genexpr)      -> 33.9 ns/op, exponent 1.00
### append then ''.join   -> 26.2 ns/op, exponent 1.00

This is a great thing to know because it is more nuanced than the folklore. CPython has an in-place resize optimization for s += t: when the target is a local variable holding the only reference to the string (refcount 1) and the opcode is STORE_FAST, it can realloc in place, making the loop linear. The moment anything else holds a reference — another variable, a list, an attribute on an object, a closure cell — the optimization is disabled and you are back to quadratic.

So the correct interview answer is: ''.join() is the reliable linear builder; += is linear only by accident and the accident is easy to break. Note the contrast with JavaScript, where += builds a rope and is genuinely fine (see JS core, section 8.4).

9.4 Set intersection iterates the smaller side

### set(n) & set(100), 20,000 times   [O(min(|s|,|t|)) -> exponent ~0]
    10,000     1577.0 ns
    20,000     1559.5 ns    -0.02
    40,000     1604.5 ns     0.04
    80,000     1545.2 ns    -0.05

### set(n) & set(n), 200 times        [both sides size n -> exponent ~1]
    10,000   161,440 ns
    20,000   337,346 ns      1.06
    40,000   671,539 ns      0.99
    80,000 1,217,764 ns      0.86

Intersecting a set of 80,000 with a set of 100 costs the same as intersecting 10,000 with 100 — O(min(len(s), len(t))), exactly as documented. Union and difference are O(len(s) + len(t)) and O(len(s)). Knowing which side is iterated lets you write small & big deliberately.

9.5 bisect.insort is not O(log n)

### bisect_left, n times (search only)      ### bisect.insort, n times
         n      ns/op   exponent                     n      ns/op   exponent
   100,000      500.5                             4,000      520.5
   200,000      538.8       1.11                  8,000     1867.2       2.84
   400,000      538.3       1.00                 16,000     3028.6       1.70
   800,000      550.8       1.03                 32,000     5791.9       1.94

The search is O(log n) (flat per-op cost), but the insert is an O(n) memmove, so building a sorted list with insort is O(n^2). Use a heap if you only need the extremum, sortedcontainers.SortedList if you need order-statistics, or collect-then-sort if you can (sorted() on 1e6 elements is 0.33 s).

9.6 Quick reference of accidental quadratics

10. Expected and probabilistic complexity

Average case averages over an input distribution; expected case averages over the algorithm’s own random choices. The second is the one you control.

Load factor. For separate chaining, the expected probe length is 1 + alpha. For open addressing with linear probing it is roughly 1/(1-alpha) for a successful search, which is why real implementations resize around alpha = 0.66 (CPython dicts) or 0.75 (Java HashMap). Above 0.9 the constant explodes.

Monte Carlo vs Las Vegas. Monte Carlo: fixed running time, possibly wrong answer (Miller-Rabin, Bloom filter). Las Vegas: always correct, running time is a random variable (randomized quicksort, skip list). Interviewers like this distinction because it maps directly onto “which risk can your system tolerate”.

Hash flooding. The O(n) worst case for a hash table is reachable by an adversary who knows your hash function — a real DoS vector against HTTP query parsing. The mitigations are randomized seeds (Python’s PYTHONHASHSEED, on by default since 3.3) and SipHash for string keys. Saying this shows you know that “O(1) average” has a security footnote.

11. Lower bounds and “can you do better?”

When an interviewer asks “can you do better?”, there are only four honest answers, and knowing which one applies is the skill.

1. Yes — here is the better algorithm. Usually via a better data structure (heap, hash map, prefix sums, monotonic stack) or by removing recomputation (DP, two pointers).

2. No, and here is the information-theoretic reason.

Comparison sorting is Omega(n log n). A comparison sort is a decision tree; each internal node is one comparison with two outcomes, and each of the n! permutations needs its own leaf. A binary tree with n! leaves has height >= log2(n!) = Theta(n log n) by Stirling. Therefore some input forces Theta(n log n) comparisons. Counting/radix/bucket sorts beat this only because they are not comparison sorts — they read the structure of the keys.

Searching an unsorted array is Omega(n). An adversary answers “not equal” for the first n-1 probes and then chooses the remaining slot to make you wrong.

Any correct algorithm must read its input. Hence Omega(n) for anything whose answer depends on every element — which is why “find the maximum” cannot be beaten, and why “find an element in a sorted array” can (you do not need to read it all).

3. Not asymptotically, but here is a constant-factor win. Fewer passes, better cache behaviour, early exit, in-place instead of allocating, bit tricks. See the stride benchmarks in section 1.

4. Only with different assumptions. “O(n) if the values are bounded integers — counting sort.” “O(1) if I can preprocess.” “O(log n) if I can keep it sorted as it arrives.” Naming the assumption is often the answer the interviewer wants.

Adversary arguments are the general tool for lower bounds: imagine an opponent who answers your queries to maximize your work, consistent with some valid input. The classic result: finding both the min and the max needs 3n/2 - 2 comparisons, not 2n - 2, because you can pair elements first.

12. Talking about complexity in the interview

A script that works:

1. Name the input size(s) explicitly. “n is the number of nodes, m the number of edges” or “n rows, k the number of distinct keys”. Half of all complexity confusion is an undefined variable.
2. State time and space. People forget space, and it is often where the follow-up lives.
3. Say how you got it. “Each element is pushed and popped at most once, so the total work in the while loop is O(n)” is worth much more than “O(n)”.
4. Say whether it is tight. “That’s Theta(n log n) — the sort dominates and I can’t avoid the sort because I need the order.”
5. Volunteer the bottleneck. “The n log n comes only from sorting; if the input arrived sorted this would be linear.” That invites the follow-up you already know the answer to.
6. Distinguish worst / average / amortized when it matters. “Hash lookups are O(1) expected; the worst case is O(n) but needs adversarial keys.”
7. Then ask about constraints. “How large is n? If it’s under a few thousand, the O(n^2) version is simpler and I’d ship that.” This is the answer of someone who has shipped code.

Verify empirically when you can: double the input and check the ratio. In an interview you can do this verbally (“if I double n this should roughly quadruple”); in real life it is the fastest way to catch a hidden linear cost, and it is exactly how every table in section 9 was produced.

# The doubling harness. Keep this in your head; it is 15 lines.
import time, math

def growth(fn, sizes, setup=lambda n: n):
    prev = None
    print(f"{'n':>12} {'seconds':>12} {'ns/op':>12} {'ratio':>8} {'exponent':>9}")
    for n in sizes:
        arg = setup(n)
        t0 = time.perf_counter(); fn(arg); dt = time.perf_counter() - t0
        ratio = dt / prev if prev else None
        exp = math.log2(ratio) if ratio else None
        print(f"{n:>12,} {dt:>12.6f} {dt/n*1e9:>12.1f} "
              f"{(f'{ratio:.2f}' if ratio else ''):>8} {(f'{exp:.2f}' if exp else ''):>9}")
        prev = dt

growth(lambda n: [x for x in range(n)], [100_000, 200_000, 400_000, 800_000])

Exponent near 0 means constant, 1 means linear, 1.0–1.2 with slow drift usually means n log n at these sizes, 2 means quadratic.

13. Interview follow-ups

Q: What is the difference between O and Theta, and why do people say O when they mean Theta?

A: O is an upper bound, Theta is tight. Colloquially “the complexity is O(n log n)” means “tight”, and interviewers accept it — but if they ask “is that tight?”, answer precisely.

Q: Is amortized O(1) the same as average O(1)?

A: No. Amortized averages over a worst-case sequence with no probability involved; average case averages over an input distribution. A dynamic array is amortized O(1) — a guarantee. A hash table is average O(1) — a probabilistic claim.

Q: Why is heapify O(n) and not O(n log n)?

A: Sift-down from the last internal node upward: nodes at height h cost O(h), and there are at most n/2^(h+1) of them. Sum over h of h·n/2^(h+1) = n·sum(h/2^h) = 2n. Most nodes are near the leaves and cost almost nothing.

Q: Why is the base of the log irrelevant?

A: log_a n = log_b n / log_b a, and 1/log_b a is a constant. In practice binary search is log2 and a B-tree of order 100 is log100, which is the same class but a 6.6x smaller constant — worth mentioning for disk-based structures.

Q: A function is O(n) but slower than one that is O(n^2). How?

A: Constants and cache behaviour. The O(n) one may allocate, chase pointers, or call through a megamorphic site; the O(n^2) one may be a tight contiguous scan. For small n the quadratic wins. See the 4x pointer-chasing penalty in section 1.

Q: What is the space complexity of recursion over a balanced binary tree? An unbalanced one?

A: O(log n) and O(n). Interviewers use this to check that you account for the stack.

Q: How do you bound a DP?

A: States x transitions. Say it in that form and also give the space after applying a rolling array, because that is the standard follow-up.

Q: What is the complexity of building a hash map from n items?

A: O(n) expected, O(n^2) adversarial worst case (all collide). Rehashing is amortized into the O(n).

Q: Sorting a nearly-sorted array?

A: Insertion sort is O(n + d) where d is the number of inversions, so O(n) for a nearly-sorted array. TimSort detects existing runs and hits O(n) too — which is exactly why both V8 and CPython use it.

Q: What is O(alpha(n))?

A: The inverse Ackermann function, the amortized cost per Union-Find operation with path compression and union by rank. It is under 5 for any n that fits in the universe, so treat it as constant but do not call it constant.

Q: Complexity of Object.keys versus Map iteration in JS?

A: Both O(n). The difference is ordering: Map is pure insertion order; object keys put integer-like keys first in ascending numeric order, then string keys in insertion order, then symbols.

Q: Why does arr.shift() matter if it is “just” a constant factor worse?

A: It is not a constant factor — it is O(n) per call, so a loop of shifts is O(n^2). That is the difference between 1e5 and 1e10 operations.

Q: What complexity should I target for n = 1e5? n = 1e9?

A: 1e5 -> O(n log n) or O(n sqrt n). 1e9 -> you cannot even read the input in a scripting language; you need O(1) or O(log n) with preprocessing, or streaming with sublinear memory.

Q: Time-space tradeoffs — give three examples.

A: Memoization (time down, space up); a hash set for O(1) lookup instead of re-scanning; a suffix automaton/prefix-sum table built once to answer many queries in O(1).

Q: What is the complexity of sorted(d.items(), key=lambda kv: kv[1])?

A: O(n log n) comparisons, but with n calls to a Python-level key function; operator.itemgetter(1) is measurably faster because it stays in C. Same asymptotics, better constant.

Q: How do you empirically confirm a complexity claim?

A: Double n and look at the ratio: ~1 means constant, ~2 linear, ~2.1–2.3 n log n, ~4 quadratic, ~8 cubic. Take log2 of the ratio to read the exponent directly.

Q: What does “in-place” mean precisely?

A: O(1) auxiliary space. In-place quicksort is a slight abuse (O(log n) stack); heapsort and insertion sort are strictly in-place; merge sort on arrays is not.

Q: Amortized vs worst case — when does the difference actually bite?

A: Real-time systems and tail latency. An amortized-O(1) hash insert that occasionally rehashes 10 million entries is a 200 ms p99.9 spike. That is why databases use incremental rehashing and games use fixed-capacity pools.

Q: What is the complexity of the sieve of Eratosthenes, and why?

A: O(n log log n) time, O(n) space. The inner loop runs n/p times per prime p, and the sum of 1/p over primes up to n is log log n.

Q: Can you sort in O(n)?

A: Not with comparisons. With bounded integer keys, counting sort is O(n + k); radix sort is O(d(n + b)) for d digits and base b. Both trade generality and space for linearity.

Q: Why is n log n the answer to so many problems?

A: Because “sort it first” is the single most productive preprocessing step, and because divide and conquer with linear merging lands exactly there by case 2 of the Master Theorem.

Next: JavaScript and Node core or, for the language-specific complexity tables applied to real structures, Data structures in TypeScript and Data structures in Python.

Verify it yourself

complexity/bench_builtins_py.py

"""Empirically measure the complexity class of Python built-ins.

For each operation we time the whole workload at n, 2n, 4n, 8n and report the
doubling ratio r = t(2n)/t(n). exponent = log2(r) is the exponent of the TOTAL
workload: 1 => linear total, 2 => quadratic total, 0 => independent of n.
"""
import gc
import math
import random
import sys
import time
from bisect import bisect_left, insort
from collections import deque
import heapq

random.seed(11)


def measure(setup, work, sizes, reps=5, ops=None):
    out = []
    for n in sizes:
        best = float("inf")
        for _ in range(reps):
            state = setup(n)
            gc.collect()
            gc.disable()
            t0 = time.perf_counter()
            work(n, state)
            dt = time.perf_counter() - t0
            gc.enable()
            best = min(best, dt)
        out.append((n, best, ops(n) if ops else n))
    return out


def report(title, rows, note=""):
    print(f"\n### {title}" + (f"   [{note}]" if note else ""))
    print(f"{'n':>10} {'seconds':>12} {'ns/op':>12} {'t(2n)/t(n)':>12} {'exponent':>10}")
    prev = None
    for n, t, k in rows:
        if prev is None:
            ratio = expo = ""
        else:
            r = t / prev
            ratio, expo = f"{r:.2f}", f"{math.log2(r):.2f}"
        print(f"{n:>10,} {t:>12.6f} {t / k * 1e9:>12.1f} {ratio:>12} {expo:>10}")
        prev = t


Q = [4_000, 8_000, 16_000, 32_000]          # quadratic-friendly sizes
L = [100_000, 200_000, 400_000, 800_000]    # linear-friendly sizes
PROBES = 200_000


# --- 1. front insertion ----------------------------------------------------
def w_insert0(n, a):
    for i in range(n):
        a.insert(0, i)


def w_appendleft(n, d):
    for i in range(n):
        d.appendleft(i)


def w_append(n, a):
    for i in range(n):
        a.append(i)


report("list.insert(0, x), n times", measure(lambda n: [], w_insert0, Q),
       "expect exponent ~2")
report("deque.appendleft(x), n times", measure(lambda n: deque(), w_appendleft, L),
       "expect exponent ~1")
report("list.append(x), n times", measure(lambda n: [], w_append, L),
       "expect exponent ~1")


# --- 2. front removal ------------------------------------------------------
def w_pop0(n, a):
    for _ in range(n):
        a.pop(0)


def w_popleft(n, d):
    for _ in range(n):
        d.popleft()


report("list.pop(0), n times", measure(lambda n: list(range(n)), w_pop0, Q),
       "expect exponent ~2")
report("deque.popleft(), n times", measure(lambda n: deque(range(n)), w_popleft, L),
       "expect exponent ~1")


# --- 3. membership ---------------------------------------------------------
def w_probe(n, st):
    coll, qs = st
    c = 0
    for q in qs:
        if q in coll:
            c += 1
    return c


report(f"`x in list` ({PROBES:,} probes, list of n)", measure(
    lambda n: (list(range(n)), [random.randrange(n) for _ in range(PROBES)]),
    w_probe, [500, 1_000, 2_000, 4_000], reps=3, ops=lambda n: PROBES),
    "cost per probe should double with n")

report(f"`x in set` ({PROBES:,} probes, set of n)", measure(
    lambda n: (set(range(n)), [random.randrange(n) for _ in range(PROBES)]),
    w_probe, [500, 1_000, 2_000, 4_000], reps=3, ops=lambda n: PROBES),
    "expect exponent ~0")

report(f"`x in dict` ({PROBES:,} probes, dict of n)", measure(
    lambda n: ({i: i for i in range(n)}, [random.randrange(n) for _ in range(PROBES)]),
    w_probe, [500, 1_000, 2_000, 4_000], reps=3, ops=lambda n: PROBES),
    "expect exponent ~0")


# --- 4. string building ----------------------------------------------------
def w_str_local(n, _):
    s = ""
    for _i in range(n):
        s += "x"
    return len(s)


def w_str_aliased(n, _):
    """Hold exactly one extra reference so the refcount==1 in-place resize in
    CPython's ceval cannot fire. O(n) memory, O(n^2) time."""
    s = ""
    prev = None
    for _i in range(n):
        prev = s          # refcount(s) == 2 at the moment of the concat
        s += "x"
    return len(s), prev is not None


def w_str_attr(n, box):
    """`obj.s += 'x'` compiles to LOAD_ATTR/STORE_ATTR, not STORE_FAST, so the
    in-place hack also cannot fire."""
    for _i in range(n):
        box.s += "x"
    return len(box.s)


class Box:
    __slots__ = ("s",)

    def __init__(self):
        self.s = ""


def w_join_gen(n, _):
    return len("".join("x" for _ in range(n)))


def w_list_join(n, _):
    parts = []
    for _i in range(n):
        parts.append("x")
    return len("".join(parts))


report("s += 'x' (plain local)", measure(lambda n: None, w_str_local, L),
       "CPython in-place resize fires -> linear")
report("s += 'x' (one extra reference alive)", measure(lambda n: None, w_str_aliased, Q),
       "in-place resize blocked -> quadratic")
report("obj.s += 'x' (attribute, not local)", measure(lambda n: Box(), w_str_attr, Q),
       "STORE_ATTR -> quadratic")
report("''.join(genexpr)", measure(lambda n: None, w_join_gen, L), "expect ~1")
report("append to list then ''.join", measure(lambda n: None, w_list_join, L), "expect ~1")


# --- 5. slicing ------------------------------------------------------------
def w_slices(n, a):
    step = max(1, n // 1000)
    t = 0
    for i in range(0, n, step):
        t += len(a[i:])
    return t


report("1000 tail slices a[i:] of a list of n", measure(
    lambda n: list(range(n)), w_slices, L, reps=3, ops=lambda n: 1000),
    "each slice copies O(n) pointers -> exponent ~1")


# --- 6. heapq / bisect -----------------------------------------------------
def w_heappush(n, h):
    for _ in range(n):
        heapq.heappush(h, random.random())


def w_bisect(n, a):
    for i in range(n):
        bisect_left(a, i)


def w_insort(n, a):
    for _ in range(n):
        insort(a, random.random())


report("heapq.heappush, n times", measure(lambda n: [], w_heappush, L),
       "n log n -- looks linear at these sizes")
report("bisect_left, n times (no insert)", measure(lambda n: list(range(n)), w_bisect, L),
       "expect ~1")
report("bisect.insort, n times", measure(lambda n: [], w_insort, Q),
       "O(log n) search + O(n) memmove -> exponent ~2")


# --- 7. set algebra --------------------------------------------------------
def w_intersect(n, st):
    big, small = st
    for _ in range(2000):
        big & small


report("set(n) & set(100), 2000 times", measure(
    lambda n: (set(range(n)), set(range(100))), w_intersect,
    [10_000, 20_000, 40_000, 80_000], reps=3, ops=lambda n: 2000),
    "O(min(|s|,|t|)) -> exponent ~0")

print(f"\n(best of 5 unless noted, GC disabled inside the timed region, "
      f"CPython {sys.version.split()[0]})")

complexity/bench_cache.py

"""'The constants are a lie' evidence.

Three experiments, all with IDENTICAL asymptotic complexity, whose wall-clock
costs differ by an order of magnitude:

  A. row-major vs column-major traversal of an n x n matrix     -- both Theta(n^2)
  B. sequential array walk vs pointer-chasing a shuffled list   -- both Theta(n)
  C. linear scan vs bisect on a sorted list                     -- O(n) vs O(log n)
     (find the crossover: below it, the "worse" algorithm wins)
"""
import gc
import random
import sys
import time
from array import array
from bisect import bisect_left

random.seed(5)


def best(fn, reps=3, *a):
    b = float("inf")
    for _ in range(reps):
        gc.collect(); gc.disable()
        t0 = time.perf_counter()
        fn(*a)
        b = min(b, time.perf_counter() - t0)
        gc.enable()
    return b


# ---------- A: matrix traversal order ----------
def make_matrix(n):
    return [array("q", range(n)) for _ in range(n)]


def row_major(m, n):
    s = 0
    for i in range(n):
        row = m[i]
        for j in range(n):
            s += row[j]
    return s


def col_major(m, n):
    s = 0
    for j in range(n):
        for i in range(n):
            s += m[i][j]
    return s


print("## A. row-major vs column-major, both Theta(n^2) (Python lists of array('q'))")
print(f"{'n':>6} {'row-major s':>14} {'col-major s':>14} {'slowdown':>10}")
for n in (512, 1024, 2048):
    m = make_matrix(n)
    tr = best(row_major, 3, m, n)
    tc = best(col_major, 3, m, n)
    print(f"{n:>6} {tr:>14.4f} {tc:>14.4f} {tc / tr:>9.2f}x")

# Same experiment with a flat buffer, so indexing cost is identical and only
# the memory access pattern differs.
print("\n## A2. flat array('q') of n*n, stride-1 vs stride-n, both Theta(n^2)")
print(f"{'n':>6} {'stride 1':>14} {'stride n':>14} {'slowdown':>10}")
for n in (512, 1024, 2048):
    buf = array("q", bytes(8 * n * n))
    def seq(buf=buf, n=n):
        s = 0
        for k in range(n * n):
            s += buf[k]
        return s
    def strided(buf=buf, n=n):
        s = 0
        for j in range(n):
            for i in range(n):
                s += buf[i * n + j]
        return s
    ts, td = best(seq, 3), best(strided, 3)
    print(f"{n:>6} {ts:>14.4f} {td:>14.4f} {td / ts:>9.2f}x")


# ---------- B: sequential vs pointer chasing ----------
print("\n## B. array walk vs pointer chasing, both Theta(n)")
print(f"{'n':>9} {'contiguous':>13} {'chased':>13} {'slowdown':>10}")
for n in (100_000, 1_000_000, 4_000_000):
    a = array("q", range(n))

    # A permutation-as-next-index chain: same number of loads, random order.
    perm = list(range(n))
    random.shuffle(perm)
    nxt = array("q", [0]) * 0
    nxt = array("q", bytes(8 * n))
    for k in range(n - 1):
        nxt[perm[k]] = perm[k + 1]
    nxt[perm[-1]] = perm[0]

    def walk(a=a, n=n):
        s = 0
        for k in range(n):
            s += a[k]
        return s

    def chase(nxt=nxt, n=n, start=perm[0]):
        s = 0
        p = start
        for _ in range(n):
            p = nxt[p]
            s += p
        return s

    tw, tc = best(walk, 3), best(chase, 3)
    print(f"{n:>9,} {tw:>13.4f} {tc:>13.4f} {tc / tw:>9.2f}x")


# ---------- C: linear scan vs binary search crossover ----------
print("\n## C. linear scan O(n) vs bisect O(log n): where is the crossover?")
print(f"{'n':>6} {'linear ns/query':>17} {'bisect ns/query':>17} {'winner':>10}")
REPS = 200_000
for n in (2, 4, 8, 16, 32, 64, 128, 256, 512):
    a = list(range(0, 2 * n, 2))
    qs = [random.randrange(0, 2 * n) for _ in range(REPS)]

    def lin(a=a, qs=qs):
        c = 0
        for q in qs:
            for i, v in enumerate(a):
                if v >= q:
                    c += i
                    break
        return c

    def bis(a=a, qs=qs):
        c = 0
        for q in qs:
            c += bisect_left(a, q)
        return c

    tl, tb = best(lin, 3), best(bis, 3)
    win = "linear" if tl < tb else "bisect"
    print(f"{n:>6} {tl / REPS * 1e9:>17.1f} {tb / REPS * 1e9:>17.1f} {win:>10}")

print(f"\n(CPython {sys.version.split()[0]}, 2-core Xeon cloud container)")

complexity/bench_cache_node.js

// Cache-effect evidence in JIT-compiled code, where memory latency is not
// hidden behind interpreter overhead.
let SINK = 0;

function best(fn, reps = 5) {
  let b = Infinity;
  for (let i = 0; i < reps; i++) {
    const t0 = process.hrtime.bigint();
    SINK += fn() & 1;
    const dt = Number(process.hrtime.bigint() - t0) / 1e9;
    if (dt < b) b = dt;
  }
  return b;
}

console.log(`# Node ${process.version} / V8 ${process.versions.v8}`);

// --- A. stride-1 vs stride-n over the same n*n Float64Array, both Theta(n^2)
console.log('\n## A. Float64Array n*n: stride 1 vs stride n (both Theta(n^2))');
console.log(`${'n'.padStart(6)} ${'MiB'.padStart(8)} ${'stride 1 s'.padStart(12)} ${'stride n s'.padStart(12)} ${'slowdown'.padStart(10)}`);
for (const n of [256, 512, 1024, 2048, 4096]) {
  const buf = new Float64Array(n * n);
  for (let i = 0; i < n * n; i++) buf[i] = i & 7;
  const seq = () => { let s = 0; for (let k = 0; k < n * n; k++) s += buf[k]; return s; };
  const str = () => { let s = 0; for (let j = 0; j < n; j++) for (let i = 0; i < n; i++) s += buf[i * n + j]; return s; };
  const ts = best(seq), td = best(str);
  console.log(
    `${String(n).padStart(6)} ${((n * n * 8) / 1048576).toFixed(1).padStart(8)} ` +
    `${ts.toFixed(5).padStart(12)} ${td.toFixed(5).padStart(12)} ${(td / ts).toFixed(2).padStart(9)}x`);
}

// --- B. sequential walk vs pointer chasing over the same number of loads
console.log('\n## B. Int32Array: sequential index walk vs random pointer chase (both Theta(n))');
console.log(`${'n'.padStart(10)} ${'MiB'.padStart(8)} ${'sequential s'.padStart(14)} ${'chased s'.padStart(12)} ${'slowdown'.padStart(10)}`);
let rs = 88172645463325252n;
function rnd32() { rs ^= rs << 13n; rs ^= rs >> 7n; rs ^= rs << 17n; return Number(rs & 0x7fffffffn); }
for (const n of [1 << 12, 1 << 16, 1 << 20, 1 << 23]) {
  const next = new Int32Array(n);
  const perm = new Int32Array(n);
  for (let i = 0; i < n; i++) perm[i] = i;
  for (let i = n - 1; i > 0; i--) { const j = rnd32() % (i + 1); const t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
  for (let k = 0; k < n - 1; k++) next[perm[k]] = perm[k + 1];
  next[perm[n - 1]] = perm[0];

  const seqArr = new Int32Array(n);
  for (let i = 0; i < n; i++) seqArr[i] = (i + 1) % n;

  const walk = () => { let s = 0; for (let k = 0; k < n; k++) s += seqArr[k]; return s; };
  const chase = () => { let s = 0, p = perm[0]; for (let k = 0; k < n; k++) { p = next[p]; s += p; } return s; };
  const tw = best(walk), tc = best(chase);
  console.log(
    `${n.toLocaleString('en-US').padStart(10)} ${((n * 4) / 1048576).toFixed(2).padStart(8)} ` +
    `${tw.toFixed(5).padStart(14)} ${tc.toFixed(5).padStart(12)} ${(tc / tw).toFixed(2).padStart(9)}x`);
}

// --- C. linear scan vs binary search crossover, both in JS
console.log('\n## C. crossover: linear scan vs binary search over a sorted Int32Array');
console.log(`${'n'.padStart(6)} ${'linear ns/q'.padStart(13)} ${'binary ns/q'.padStart(13)} ${'winner'.padStart(8)}`);
const Q = 2_000_000;
for (const n of [2, 4, 8, 16, 32, 64, 128, 256, 1024, 4096]) {
  const a = new Int32Array(n);
  for (let i = 0; i < n; i++) a[i] = 2 * i;
  const qs = new Int32Array(Q);
  for (let i = 0; i < Q; i++) qs[i] = rnd32() % (2 * n);

  const lin = () => {
    let c = 0;
    for (let t = 0; t < Q; t++) { const q = qs[t]; let i = 0; while (i < n && a[i] < q) i++; c += i; }
    return c;
  };
  const bin = () => {
    let c = 0;
    for (let t = 0; t < Q; t++) {
      const q = qs[t]; let lo = 0, hi = n;
      while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < q) lo = mid + 1; else hi = mid; }
      c += lo;
    }
    return c;
  };
  const tl = best(lin, 3), tb = best(bin, 3);
  console.log(
    `${String(n).padStart(6)} ${((tl / Q) * 1e9).toFixed(2).padStart(13)} ` +
    `${((tb / Q) * 1e9).toFixed(2).padStart(13)} ${(tl < tb ? 'linear' : 'binary').padStart(8)}`);
}
console.error('sink', SINK);

complexity/bench_crossover.py

"""Where does an O(log n) algorithm actually beat an O(n) one?

Three fair fights (same implementation language on both sides) plus one unfair
fight, to show that the crossover point is a property of constants, not of the
asymptotics.
"""
import gc
import random
import time
from bisect import bisect_left

random.seed(9)
REPS = 100_000


def best(fn, reps=3):
    b = float("inf")
    for _ in range(reps):
        gc.collect(); gc.disable()
        t0 = time.perf_counter()
        fn()
        b = min(b, time.perf_counter() - t0)
        gc.enable()
    return b


def py_bisect(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) >> 1
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


print("## Fair fight 1: pure-Python linear scan vs pure-Python binary search")
print(f"{'n':>6} {'linear ns/q':>13} {'binary ns/q':>13} {'winner':>8}")
for n in (2, 4, 8, 16, 24, 32, 48, 64, 128, 512):
    a = list(range(0, 2 * n, 2))
    qs = [random.randrange(0, 2 * n) for _ in range(REPS)]

    def lin(a=a, qs=qs):
        c = 0
        for q in qs:
            for i, v in enumerate(a):
                if v >= q:
                    c += i
                    break
        return c

    def binr(a=a, qs=qs):
        c = 0
        for q in qs:
            c += py_bisect(a, q)
        return c

    tl, tb = best(lin), best(binr)
    print(f"{n:>6} {tl/REPS*1e9:>13.1f} {tb/REPS*1e9:>13.1f} "
          f"{('linear' if tl < tb else 'binary'):>8}")

print("\n## Fair fight 2: C-level linear scan (list.index) vs C-level bisect_left")
print(f"{'n':>6} {'index ns/q':>13} {'bisect ns/q':>13} {'winner':>8}")
for n in (2, 4, 8, 16, 32, 64, 128, 256, 512, 2048):
    a = list(range(n))
    qs = [random.randrange(n) for _ in range(REPS)]

    def idx(a=a, qs=qs):
        c = 0
        for q in qs:
            c += a.index(q)
        return c

    def bis(a=a, qs=qs):
        c = 0
        for q in qs:
            c += bisect_left(a, q)
        return c

    ti, tb = best(idx), best(bis)
    print(f"{n:>6} {ti/REPS*1e9:>13.1f} {tb/REPS*1e9:>13.1f} "
          f"{('index' if ti < tb else 'bisect'):>8}")

print("\n## Fair fight 3: dict build+lookup vs sort+bisect for k lookups over n items")
print(f"{'n':>8} {'k':>8} {'hash total s':>14} {'sort+bisect s':>15} {'winner':>8}")
for n, k in ((1000, 1), (1000, 10), (1000, 1000), (100_000, 1), (100_000, 100_000)):
    data = [random.randrange(1 << 30) for _ in range(n)]
    qs = [random.choice(data) for _ in range(k)]

    def hashway(data=data, qs=qs):
        s = set(data)
        return sum(1 for q in qs if q in s)

    def sortway(data=data, qs=qs):
        a = sorted(data)
        c = 0
        for q in qs:
            i = bisect_left(a, q)
            c += 1 if i < len(a) and a[i] == q else 0
        return c

    th, ts = best(hashway), best(sortway)
    print(f"{n:>8,} {k:>8,} {th:>14.6f} {ts:>15.6f} "
          f"{('hash' if th < ts else 'sort'):>8}")

print("\n## Unfair fight: bytecode linear scan vs C bisect (why 'C wins' is not an argument)")
print(f"{'n':>6} {'py-linear ns/q':>16} {'C bisect ns/q':>15} {'winner':>8}")
for n in (2, 8, 64):
    a = list(range(0, 2 * n, 2))
    qs = [random.randrange(0, 2 * n) for _ in range(REPS)]

    def lin(a=a, qs=qs):
        c = 0
        for q in qs:
            for i, v in enumerate(a):
                if v >= q:
                    c += i
                    break
        return c

    def bis(a=a, qs=qs):
        c = 0
        for q in qs:
            c += bisect_left(a, q)
        return c

    tl, tb = best(lin), best(bis)
    print(f"{n:>6} {tl/REPS*1e9:>16.1f} {tb/REPS*1e9:>15.1f} "
          f"{('py-linear' if tl < tb else 'C bisect'):>8}")

complexity/bench_fixups_py.py

import gc
import math
import random
import sys
import time

random.seed(3)


def measure(setup, work, sizes, reps=5, ops=None):
    out = []
    for n in sizes:
        best = float("inf")
        for _ in range(reps):
            state = setup(n)
            gc.collect(); gc.disable()
            t0 = time.perf_counter()
            work(n, state)
            dt = time.perf_counter() - t0
            gc.enable()
            best = min(best, dt)
        out.append((n, best, ops(n) if ops else n))
    return out


def report(title, rows, note=""):
    print(f"\n### {title}" + (f"   [{note}]" if note else ""))
    print(f"{'n':>10} {'seconds':>12} {'ns/op':>12} {'t(2n)/t(n)':>12} {'exponent':>10}")
    prev = None
    for n, t, k in rows:
        ratio = expo = ""
        if prev is not None:
            r = t / prev
            ratio, expo = f"{r:.2f}", f"{math.log2(r):.2f}"
        print(f"{n:>10,} {t:>12.6f} {t / k * 1e9:>12.1f} {ratio:>12} {expo:>10}")
        prev = t


def w_str_aliased(n, _):
    s = ""
    prev = None
    for _i in range(n):
        prev = s
        s += "x"
    return len(s), prev is not None


def w_str_local(n, _):
    s = ""
    for _i in range(n):
        s += "x"
    return len(s)


BIGQ = [25_000, 50_000, 100_000, 200_000]
report("s += 'x' (one extra reference alive)", measure(lambda n: None, w_str_aliased, BIGQ, reps=3),
       "in-place resize blocked -> quadratic")
report("s += 'x' (plain local, same n range)", measure(lambda n: None, w_str_local, BIGQ, reps=3),
       "in-place resize fires -> linear")


def w_intersect(n, st):
    big, small = st
    acc = 0
    for _ in range(20_000):
        acc += len(big & small)
    return acc


report("set(n) & set(100), 20,000 times", measure(
    lambda n: (set(range(n)), set(range(100))), w_intersect,
    [10_000, 20_000, 40_000, 80_000], reps=5, ops=lambda n: 20_000),
    "O(min(|s|,|t|)) -> exponent ~0")


def w_intersect_rev(n, st):
    big, small = st
    acc = 0
    for _ in range(200):
        acc += len(big & small)
    return acc


report("set(n) & set(n), 200 times", measure(
    lambda n: (set(range(n)), set(range(n // 2, n + n // 2))), w_intersect_rev,
    [10_000, 20_000, 40_000, 80_000], reps=5, ops=lambda n: 200),
    "both sides size n -> exponent ~1")

print(f"\n(CPython {sys.version.split()[0]})")

complexity/bench_list_growth.py

"""Measure CPython's list over-allocation pattern with sys.getsizeof, and
derive the amortized cost of append."""
import sys

EMPTY = sys.getsizeof([])
PTR = 8  # bytes per PyObject* on 64-bit

print(f"sys.getsizeof([])          = {EMPTY} bytes  (header only)")
print(f"sys.getsizeof([1])         = {sys.getsizeof([1])} bytes")
print(f"pointer size               = {PTR} bytes\n")

a = []
last = sys.getsizeof(a)
reallocs = []
print(f"{'len':>8} {'getsizeof':>10} {'capacity':>10}   event")
for i in range(0, 200):
    a.append(i)
    sz = sys.getsizeof(a)
    if sz != last:
        cap = (sz - EMPTY) // PTR
        reallocs.append((len(a), cap))
        if len(reallocs) <= 18:
            print(f"{len(a):>8} {sz:>10} {cap:>10}   grow")
        last = sz

# keep going to large n to expose the asymptotic growth factor
a = []
last = sys.getsizeof(a)
pts = []
for i in range(1_000_000):
    a.append(i)
    sz = sys.getsizeof(a)
    if sz != last:
        pts.append(((sz - EMPTY) // PTR))
        last = sz

print(f"\ntotal reallocations while appending 1,000,000 items: {len(pts)}")
print("capacity sequence (first 24):", pts[:24])
print("capacity sequence (last 8):  ", pts[-8:])
ratios = [pts[i + 1] / pts[i] for i in range(len(pts) - 1)]
print(f"growth ratio: first={ratios[0]:.3f} median={sorted(ratios)[len(ratios)//2]:.5f} "
      f"last={ratios[-1]:.5f}")
print(f"asymptotic factor approaches {pts[-1]/pts[-2]:.6f}  (CPython: new = n + n>>3 + 6, rounded)")

# Verify the documented formula: new_allocated = ((n >> 3) + (n < 9 ? 3 : 6)) + n
def predict(n):
    return (n + (n >> 3) + (3 if n < 9 else 6)) & ~3 if False else n + (n >> 3) + (3 if n < 9 else 6)

print("\ncheck CPython list_resize formula  new_alloc = n + (n>>3) + (n<9 ? 3 : 6):")
b = []
mismatch = 0
prev_cap = 0
for n in range(0, 3000):
    b.append(n)
    cap = (sys.getsizeof(b) - EMPTY) // PTR
    if cap != prev_cap:
        want = predict(len(b))
        # CPython rounds the allocation up to a multiple of 4
        want_rounded = (want + 3) & ~3
        flag = "ok" if cap in (want, want_rounded) else "MISMATCH"
        if flag == "MISMATCH":
            mismatch += 1
            if mismatch < 6:
                print(f"  len={len(b)} cap={cap} predicted={want}/{want_rounded}")
        prev_cap = cap
print(f"  mismatches in first 3000 appends: {mismatch}")

# Amortized cost: total elements copied over 1e6 appends
total_copied = 0
prev = 0
for cap in pts:
    total_copied += prev
    prev = cap
print(f"\nelements copied during 1,000,000 appends: {total_copied:,} "
      f"({total_copied/1_000_000:.3f} per append)")

complexity/bench_n_in_1s_node.js

// For each complexity class, find the largest n whose work finishes in ~1.0 s
// on Node 22 / V8. Every kernel returns a value that is accumulated into a
// global sink and printed at the end, so V8 cannot eliminate the loops.

const BUDGET = 1.0;
let SINK = 0;

function bestOf(fn, arg, reps = 5) {
  let b = Infinity;
  for (let k = 0; k < reps; k++) {
    const t0 = process.hrtime.bigint();
    SINK += Number(fn(arg)) & 1;
    const dt = Number(process.hrtime.bigint() - t0) / 1e9;
    if (dt < b) b = dt;
  }
  return b;
}

const kLinear = (n) => { let s = 0; for (let i = 0; i < n; i++) s += i; return s; };
const kSqrt = (n) => { let i = 2, s = 0; while (i * i <= n) { s += n % i; i++; } return s; };
const kLogn = (n) => {
  let total = 0;
  for (let r = 0; r < 200000; r++) { let m = n; while (m > 1) { m = Math.floor(m / 2); total++; } }
  return total;
};
const kQuad = (n) => { let s = 0; for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) s += (i ^ j) & 1; return s; };
const kCubic = (n) => { let s = 0; for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) for (let k = 0; k < n; k++) s += (i ^ j ^ k) & 1; return s; };
const kExp = (n) => { let s = 0; const lim = 1 << n; for (let m = 0; m < lim; m++) s += m & 1; return s; };

function permCount(n) { // O(n!) via Heap's algorithm, real work per permutation
  const a = Array.from({ length: n }, (_, i) => i);
  const c = new Array(n).fill(0);
  let s = a[0], i = 0;
  while (i < n) {
    if (c[i] < i) {
      const j = i % 2 === 0 ? 0 : c[i];
      const t = a[j]; a[j] = a[i]; a[i] = t;
      s += a[0];
      c[i]++; i = 0;
    } else { c[i] = 0; i++; }
  }
  return s;
}

let rngState = 123456789;
function rnd() { rngState ^= rngState << 13; rngState ^= rngState >>> 17; rngState ^= rngState << 5; return rngState >>> 0; }

function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const L = mergeSort(a.slice(0, mid)), R = mergeSort(a.slice(mid));
  const out = []; let i = 0, j = 0;
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);
  while (i < L.length) out.push(L[i++]);
  while (j < R.length) out.push(R[j++]);
  return out;
}

function timeMergeSort(n) {
  const a = Array.from({ length: n }, () => rnd());
  const t0 = process.hrtime.bigint();
  const r = mergeSort(a);
  const dt = Number(process.hrtime.bigint() - t0) / 1e9;
  SINK += r[0] & 1;
  return dt;
}

function timeNativeSort(n) {
  const a = Array.from({ length: n }, () => rnd());
  const t0 = process.hrtime.bigint();
  a.sort((x, y) => x - y);
  const dt = Number(process.hrtime.bigint() - t0) / 1e9;
  SINK += a[0] & 1;
  return dt;
}

function lgamma(x) { // Lanczos, good enough for factorial extrapolation
  const g = 7;
  const c = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,
    771.32342877765313, -176.61502916214059, 12.507343278686905,
    -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7];
  if (x < 0.5) return Math.log(Math.PI / Math.sin(Math.PI * x)) - lgamma(1 - x);
  x -= 1;
  let a = c[0];
  const t = x + g + 0.5;
  for (let i = 1; i < g + 2; i++) a += c[i] / (x + i);
  return 0.5 * Math.log(2 * Math.PI) + (x + 0.5) * Math.log(t) - t + Math.log(a);
}

function solveN(n0, t0, kind) {
  const r = BUDGET / t0;
  switch (kind) {
    case 'logn': return Math.pow(n0, r);
    case 'sqrt': return n0 * r * r;
    case 'n': return n0 * r;
    case 'nlogn': {
      const target = r * n0 * Math.log2(n0);
      let lo = 2, hi = 1e18;
      for (let i = 0; i < 300; i++) {
        const mid = (lo + hi) / 2;
        if (mid * Math.log2(mid) < target) lo = mid; else hi = mid;
      }
      return lo;
    }
    case 'n2': return n0 * Math.sqrt(r);
    case 'n3': return n0 * Math.cbrt(r);
    case '2n': return n0 + Math.log2(r);
    case 'fact': {
      const target = lgamma(n0 + 1) + Math.log(r);
      let x = n0;
      while (lgamma(x + 2) <= target) x++;
      return x;
    }
  }
}

const fmt = (x) => (!Number.isFinite(x) || x > 1e30 ? 'effectively unbounded' : x > 1e15 ? x.toPrecision(3) : Math.floor(x).toLocaleString('en-US'));

const rows = [['O(1)', '-', '-', 'unbounded']];
for (const [label, kind, n0, fn] of [
  ['O(log n)', 'logn', 1 << 20, kLogn],
  ['O(sqrt n)', 'sqrt', 1e8, kSqrt],
  ['O(n)', 'n', 30000000, kLinear],
  ['O(n^2)', 'n2', 10000, kQuad],
  ['O(n^3)', 'n3', 700, kCubic],
  ['O(2^n)', '2n', 25, kExp],
  ['O(n!)', 'fact', 11, permCount],
]) {
  const t = bestOf(fn, n0);
  rows.push([label, n0.toLocaleString('en-US'), t.toFixed(4), fmt(solveN(n0, t, kind))]);
}

let tms = Infinity;
for (let i = 0; i < 3; i++) tms = Math.min(tms, timeMergeSort(500000));
rows.push(['O(n log n) hand-merge', '500,000', tms.toFixed(4), fmt(solveN(500000, tms, 'nlogn'))]);

let tns = Infinity;
for (let i = 0; i < 3; i++) tns = Math.min(tns, timeNativeSort(2000000));
rows.push(['O(n log n) .sort()', '2,000,000', tns.toFixed(4), fmt(solveN(2000000, tns, 'nlogn'))]);

const order = ['O(1)', 'O(log n)', 'O(sqrt n)', 'O(n)', 'O(n log n) hand-merge',
  'O(n log n) .sort()', 'O(n^2)', 'O(n^3)', 'O(2^n)', 'O(n!)'];
rows.sort((a, b) => order.indexOf(a[0]) - order.indexOf(b[0]));

console.log(`# Node ${process.version} / V8 ${process.versions.v8} -- budget ${BUDGET}s`);
console.log(`${'class'.padEnd(22)} | ${'calib n'.padStart(12)} | ${'measured s'.padStart(10)} | ${'max n in 1s'.padStart(20)}`);
console.log('-'.repeat(74));
for (const [a, b, c, d] of rows) {
  console.log(`${a.padEnd(22)} | ${b.padStart(12)} | ${c.padStart(10)} | ${d.padStart(20)}`);
}
console.error(`sink=${SINK}`);