Data structures and algorithms fundamentals

An upper bound on how the cost grows as the input grows, with constant factors and lower-order terms deliberately discarded. So O(n) says the work grows roughly in proportion to the input, not that it takes n operations. Discarding the constants is what makes it useful for comparing algorithms and what makes it misleading in production, where an O(n log n) algorithm with a huge constant can lose to an O(n²) one at the sizes you actually run. State the bound, then say what the constants are doing if it matters.

Worst case is the cost on the least favourable input of that size, which is what Big-O usually reports. Average case assumes a distribution over inputs, which means it depends on an assumption you should state. Amortised is different in kind: it is the average per operation across a worst-case sequence, so it is a guarantee rather than a probabilistic claim. A dynamic array's append is amortised constant because the occasional doubling is paid for by the cheap appends around it.

Each doubling copies everything, which looks expensive until you total the copying across a whole sequence of appends.

appends:   1  2  3  4  5  6  7  8  9 ...
capacity:  1  2  4  4  8  8  8  8 16 ...
copies:    -  1  2  -  4  -  -  -  8 ...

Total copying to reach n elements: 1 + 2 + 4 + ... + n/2  <  n
So n appends cost fewer than 2n operations -> O(1) each, amortised.

The sum of a doubling series is less than its final term, which is the whole argument. Any growth factor greater than one gives the same result; growing by a fixed amount does not.

# Growing by one each time: every append copies everything.
# 1 + 2 + 3 + ... + n = n(n+1)/2 operations -> O(n) per append, O(n^2) total.

Two consequences worth carrying. Amortised constant is not the same as constant: a single append can take O(n), so it is the wrong guarantee for a real-time system where one slow operation matters more than a good average. And if you know the final size, preallocating avoids the copying entirely — the same reasoning that makes sizing a hash map at construction worthwhile.

Four recur. Naming the wrong n, when a problem has two dimensions such as rows and columns, or a list of strings where sorting costs comparisons times string length. Forgetting space the language allocates for you, particularly the recursion stack and the copies made by slicing. Confusing the cost of a call with the cost of what it does, so a membership test that is constant on a set and linear on a list looks identical in code. And stopping at the bound without checking it against the stated input limits.

They are given to you for free and eliminate whole families in a sentence. A limit of about twenty invites an exponential solution over subsets. A few thousand accommodates quadratic, which usually means a two-dimensional dynamic-programming table. A hundred thousand rules out quadratic and points at sorting, a single pass with a structure, or something logarithmic per element. A billion means you are not iterating at all and the answer is mathematical.

A property your code guarantees is true between steps — the window contains at most one of each character, everything left of the pointer is already sorted, the heap's root is the smallest element. It matters because it is the difference between an argument for correctness and a hope. A candidate who names the invariant has designed the solution; one who cannot has recalled it, and the distinction shows immediately when the interviewer changes a constraint.

That the work halves at each step, which is why binary search, balanced trees and heap operations all land there. The practical significance is how flat it is: doubling the input adds one step, so a structure with logarithmic operations scales to enormous sizes without meaningful slowdown. Log base is irrelevant in Big-O because changing base is a constant factor, which is why nobody writes log₂.

Count the work at each level and multiply by the number of levels — that single habit covers most divide-and-conquer analysis.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])      # T(n/2)
    right = merge_sort(items[mid:])     # T(n/2)
    return merge(left, right)           # O(n) to merge

level 0:  one problem of size n        -> n work
level 1:  two of size n/2              -> n work
level 2:  four of size n/4             -> n work
...
level k:  n problems of size 1         -> n work

Levels: how many halvings reach 1, which is log2(n).
Total:  n work per level x log n levels = O(n log n)

The space is the part people miss. The slicing in the code above copies at every level, so it allocates O(n log n) in total over the run. Peak live space is still O(n), because sibling calls are sequential rather than concurrent - the same order as an in-place merge sort's buffer, with a much worse constant and far more allocator pressure. The recursion stack adds O(log n) on top.

The same counting applies when the branching factor and the shrinkage differ. A recursion making two calls on n−1 has 2ⁿ nodes, which is why naive Fibonacci is exponential — the tree is wide and deep. Recognising that shape in a call tree is what tells you memoisation will collapse it.