Overview

Every algorithmic choice a quant makes — resort the whole book every tick or maintain a heap, scan a list or hash it, recompute a covariance matrix from scratch or update it incrementally — is a bet about how a running-time function grows as the input grows. This topic builds the language for making that bet precisely instead of by folklore: asymptotic notation ($O$, $\Omega$, $\Theta$) to classify growth rates, the divide-and-conquer pattern and the recurrences it generates, the master theorem as the standard tool for solving those recurrences without reinventing a proof each time, and probabilistic analysis for algorithms whose running time depends on the input's order, not just its size. Every later topic in this unit — sorting, hashing, trees, graphs, dynamic programming — states its cost in this language and, in several cases (mergesort, the union-find bound, randomized quicksort), reuses the exact recurrence-solving and probabilistic-analysis machinery built here.