Complexity & Analysis

Big-O, Omega, and Theta, tight vs loose bounds, best, average, and worst case, and comparing growth rates.

Writing recurrences, recursion trees, the master theorem cases, and the substitution method.

Aggregate, accounting, and potential methods on the doubling array, the two-stack queue, and path compression.

Auxiliary space, the call stack, recursion depth and stack overflow, in-place claims, and tail calls.

Cache locality, pointer chasing vs contiguous memory, branch and allocation cost, and operations-per-second budgets.