Complexity, honestly

Start empty and do n appends. Resizes happen at sizes 1, 2, 4, 8, …, up to the last power of two below n. The copying work is the sum of those sizes:

1 + 2 + 4 + 8 + ... + 2^k  where 2^k < n

That is a geometric series, and it sums to 2^(k+1) - 1 < 2n. Add the n constant-time writes and total work is under 3n. Divide by n operations: under 3 per operation, a constant. That is the whole proof.

// The doubling argument, measured rather than asserted.
function appendsWithCopyCount(n) {
  let capacity = 1;
  let size = 0;
  let copies = 0;
  for (let i = 0; i < n; i++) {
    if (size === capacity) {
      copies += size;      // copy every existing element into the new buffer
      capacity *= 2;
    }
    size++;
  }
  return copies;
}

for (const n of [10, 100, 1000, 100000, 1000000]) {
  const copies = appendsWithCopyCount(n);
  console.log(`n=${String(n).padStart(7)}  copies=${String(copies).padStart(7)}  copies/n=${(copies / n).toFixed(3)}`);
}

# The doubling argument, measured rather than asserted.
def appends_with_copy_count(n):
    capacity = 1
    size = 0
    copies = 0
    for _ in range(n):
        if size == capacity:
            copies += size      # copy every existing element into the new buffer
            capacity *= 2
        size += 1
    return copies


for n in [10, 100, 1000, 100000, 1000000]:
    copies = appends_with_copy_count(n)
    print(f"n={str(n).rjust(7)}  copies={str(copies).rjust(7)}  copies/n={copies / n:.3f}")

n=     10  copies=     15  copies/n=1.500
n=    100  copies=    127  copies/n=1.270
n=   1000  copies=   1023  copies/n=1.023
n= 100000  copies= 131071  copies/n=1.311
n=1000000  copies=1048575  copies/n=1.049

Run it: the ratio hovers just under 1 and never grows, no matter how large n gets. That bounded ratio is the meaning of amortised O(1).

Now change capacity *= 2 to capacity += 1 and run it again. The ratio stops being constant and starts growing linearly, because the total copying becomes 1 + 2 + ... + n ≈ n²/2. Growing by a constant amount gives amortised O(n) per append. Growing by a constant factor gives amortised O(1). Any factor above 1 works — implementations use values from 1.125 to 2, trading memory slack against copy frequency.

They are not synonyms, and mixing them up is a tell.

Amortised is a worst-case guarantee over a sequence: any n operations cost O(n) total. No adversary can defeat it, because the accounting is airtight.

Average case is a claim about a distribution of inputs. Hash table lookup is O(1) on average, assuming keys distribute well. An adversary who knows your hash function can choose keys that all collide and make every lookup O(n) — the algorithmic complexity attack that pushed language runtimes toward randomised hashing.

So: dynamic array append is amortised O(1) and no input can break it. Hash lookup is average O(1) and a chosen input can. Both get called "O(1)" in conversation; only one of them survives an adversary.

The six claims candidates get wrong

That last row is the entire idea behind the next three lessons: a nested loop whose inner pointer only ever moves forward touches each element a bounded number of times, and is therefore linear. Counting loop nesting levels is a heuristic. Counting how many times each element is touched is the actual analysis.

Reading the bound backwards

Given a constraint, you can usually infer the intended solution class. This table is worth knowing cold, because it turns "I'm stuck" into "I'm looking for the wrong shape of answer".

The bottom row is the one people miss. When a bound is absurdly large — 10¹⁸ — the input cannot even be read, so the answer is not an algorithm over the input at all. It is closed form, or binary search over the answer space, or fast exponentiation.

Space, which people forget to state

Say the space bound unprompted; roughly half of candidates don't, and it is an explicit rubric line at several companies.

Count only what you allocate beyond the input. A hash set of distinct characters over a fixed alphabet is O(1) — 128 slots is 128 slots whether the string is ten characters or ten million. A hash set of elements is O(n). Recursion costs O(depth) in stack frames whether or not you allocated anything, and an in-place algorithm that recurses is not O(1) space.