Chapter 1: Python Foundations

Python lists are dynamic arrays: internally a contiguous C array of PyObject* pointers. Random access is $O(1)$ since lst[i] computes base_addr + i * 8. append() is amortized $O(1)$ due to over-allocation — when the array fills, Python grows it by roughly $12.5\%$ plus a constant. insert(0, x) is $O(n)$ because every pointer must shift right. pop() from the end is $O(1)$; pop(0) is $O(n)$. For frequent front operations, collections.deque provides $O(1)$ at both ends using a doubly-linked list of fixed-size blocks.

Slicing lst[a:b] creates a new list by copying $b - a$ pointers, so it is $O(b - a)$ in time and space. The exclusive-stop convention ensures $\text{len}(\texttt{lst[a:b]}) = b - a$ and that lst[:k] + lst[k:] reconstructs the original list for any $k$. Negative indexing is syntactic sugar: lst[-i] maps to lst[len(lst) - i] at $O(1)$. Stride slicing lst[::s] selects every $s$-th element, producing $\lceil n/s \rceil$ elements. NumPy arrays differ fundamentally: slices return views (shared memory) rather than copies, making them $O(1)$ but requiring caution with mutation.

List comprehensions compile to dedicated LIST_APPEND bytecodes that bypass the overhead of list.append() method lookups, making them $1.5$–$3\times$ faster than equivalent for loops. Memory usage is $O(n)$ for the output list. For large datasets, generator expressions (expr for x in iterable) use $O(1)$ memory by yielding items lazily. Nested comprehensions [f(x) for row in matrix for x in row] execute left-to-right — the outer loop runs first. The time complexity of a filtered comprehension [x for x in data if p(x)] is $O(n \cdot C_p)$ where $C_p$ is the cost of the predicate.

Tuples are immutable fixed-size arrays — their memory is allocated in a single block of $56 + 8n$ bytes (for $n$ elements), slightly smaller than lists which need extra space for growth. Because tuples are immutable and hashable (when all elements are hashable), they can serve as dictionary keys. Sets use a hash table with open addressing: membership testing x in s is $O(1)$ amortized. Set operations exploit hash-based algorithms: intersection is $O(\min(|A|, |B|))$, union is $O(|A| + |B|)$, and difference is $O(|A|)$. The load factor is kept below $2/3$; exceeding it triggers a resize to $8 \times$ or $4 \times$ capacity.

Python dicts use open addressing with a compact hash table. Lookup is $O(1)$ amortized, but worst-case $O(n)$ with hash collisions. The load factor triggers resizing at $2/3$ capacity, growing to $4\times$ or $8\times$ the current size. Since Python 3.7, dicts preserve insertion order by storing entries in a dense array with a separate sparse index table — this reduces memory by $\sim 25\%$ compared to the old design. The hash function for integers is the identity (for small values), while strings use SipHash for security against hash-flooding attacks.

dict.get(key, default) is $O(1)$ average — it computes the hash, probes the table, and returns the default if the slot is empty, avoiding the exception overhead of KeyError. dict.items() returns a view object backed by the same underlying data — iterating it is $O(n)$ but creating the view is $O(1)$. The in operator on a dict checks keys only (not values) and is $O(1)$ amortized. dict.update(other) merges in $O(m)$ where $m$ is the size of other, and Python 3.9+ supports d1 | d2 merge syntax which creates a new dict in $O(n + m)$.

Dict comprehensions {k: v for ...} pre-size the hash table when the input length is known, avoiding repeated resizing. Building a histogram via {val: data.count(val) for val in set(data)} is $O(n \cdot k)$ where $k$ is the number of unique values, because list.count() is $O(n)$ per call. The efficient alternative is a single-pass loop with dict.get() at $O(n)$ total, or collections.Counter(data) which is implemented in C and even faster. Inverting a dict {v: k for k, v in d.items()} is $O(n)$ but only produces a valid inverse if all values are unique and hashable.

Nested dicts form a tree structure where each level of nesting adds one hash-table lookup. Accessing d[k1][k2][k3] performs three $O(1)$ lookups for $O(1)$ total. defaultdict(list) overrides __missing__ to auto-create entries, using the factory function to construct the default value — this is $O(1)$ per missing-key access. Memory overhead compounds with nesting: each dict object costs $\sim 232$ bytes (empty) plus $\sim 72$ bytes per entry. For deep hierarchies, consider json-style access patterns or dataclasses to reduce overhead. ChainMap provides $O(k)$ lookup across $k$ dicts without merging them.

Python evaluates if/elif/else chains sequentially — each branch is tested in order, so the worst case for $k$ branches is $O(k)$ condition checks. Short-circuit evaluation in and/or skips the right operand when the result is determined: False and expensive() never calls expensive(). The ternary x if cond else y compiles to a single JUMP_IF_FALSE bytecode followed by a POP — it is not syntactic sugar for an if-statement but a genuine expression that evaluates to a value. Match-case (Python 3.10+) uses a sequence of pattern checks, currently $O(k)$ for $k$ patterns, though future optimizations may use jump tables.

Python's for loop calls iter() on the iterable (invoking __iter__), then repeatedly calls __next__() until StopIteration is raised. Each iteration has $\sim 50$ns overhead from the interpreter loop. enumerate(iterable) wraps the iterator and maintains a counter with zero additional memory beyond an integer. zip(a, b) interleaves calls to next() on both iterators, stopping at the shortest — its overhead is $O(\min(|a|, |b|))$. For performance-critical inner loops, pushing work into NumPy vectorized operations eliminates the per-iteration Python overhead entirely.

while loops check a condition before each iteration — each check involves evaluating the condition expression and a POP_JUMP_IF_FALSE bytecode. break compiles to BREAK_LOOP, which unwinds the block stack to the nearest loop. continue jumps directly to the condition check. The while True: ... break pattern is common for "loop-and-a-half" problems where the exit condition is computed mid-body. Convergence loops like while error > tol terminate when the error sequence $\{e_k\}$ decreases below the tolerance — for gradient descent with learning rate $\alpha$, this takes $O(1/\alpha)$ iterations for convex objectives.

range(start, stop, step) is a lazy sequence object that computes elements on demand using $O(1)$ memory regardless of the range size. Membership testing x in range(...) is also $O(1)$ — it checks $\text{start} \leq x < \text{stop}$ and $(x - \text{start}) \bmod \text{step} = 0$ arithmetically rather than iterating. range supports negative steps for reverse iteration. enumerate(iterable, start=0) produces $(\text{index}, \text{value})$ tuples with $O(1)$ overhead per iteration. The length of range(a, b, s) is $\max(0, \lceil (b - a) / s \rceil)$.

Python functions are first-class objects: def creates a function object and binds it to the name in the local namespace. The function body is compiled to bytecode once at definition time and stored in func.__code__. Each call creates a new stack frame ($\sim 400$ bytes), binds arguments, and executes the bytecode. Function call overhead is $\sim 100$–$200$ns in CPython. return pops the frame and passes the result to the caller. Returning multiple values as a tuple is $O(k)$ for $k$ values — Python does not copy the values, just creates a tuple of references.

Default argument values are evaluated once at function definition time and stored in func.__defaults__. This is why mutable defaults (lists, dicts) are shared across calls — each invocation sees the same object. The standard fix def f(x=None): if x is None: x = [] evaluates the default at call time. Keyword arguments are matched by name using a dict-based lookup internally. *args packs extra positionals into a tuple ($O(k)$ to construct), and **kwargs packs extra keywords into a dict ($O(k)$). Argument unpacking f(*args, **kwargs) is also $O(k)$.

*args collects excess positional arguments into a tuple — since tuples are immutable, this is safe to store without copying. **kwargs collects excess keyword arguments into a regular dict. When forwarding with func(*args, **kwargs), Python unpacks the tuple and dict back into the function's parameter slots. The total cost is $O(k)$ where $k$ is the number of arguments. This pattern enables the Decorator pattern: a wrapper that accepts any signature can transparently forward all arguments. The functools.wraps decorator preserves the original function's __name__ and __doc__ on the wrapper.

Lambda expressions compile to the same MAKE_FUNCTION bytecode as def — they produce identical function objects with the same call overhead. The only difference is syntactic: lambdas are limited to a single expression (no statements, no assignments). Lambdas create closures over enclosing variables, capturing them by reference, not by value — the classic loop pitfall [lambda: i for i in range(5)] creates five functions all referencing the final value of i. The fix is a default argument: lambda i=i: i. In terms of complexity, a lambda passed to sorted(key=...) is called $O(n \log n)$ times during the sort.

A pure function maps input to output deterministically with no side effects: $f(x) = y$ always. Referential transparency means any call $f(x)$ can be replaced by its result $y$ without changing the program's behavior. Pure functions enable memoization — caching results in a lookup table turns repeated calls from $O(C_f)$ to $O(1)$ at the cost of $O(n)$ memory for $n$ unique inputs. In ML, pure preprocessing functions guarantee reproducibility: given the same data and random seed, the output is identical. Impure functions that mutate inputs (like in-place operations X -= mean) create hidden dependencies that break parallelism and caching.

A Python class creates a new type object via the type metaclass. Instance creation involves two steps: __new__ allocates memory (typically $\sim 56$ bytes base + $8$ bytes per __dict__ slot), and __init__ initializes attributes. Instance attributes are stored in a per-object __dict__ (a regular dict). With __slots__ = ['x', 'y'], Python skips the dict and uses fixed-offset struct members — saving $\sim 100$ bytes per instance and making attribute access $\sim 20\%$ faster. Method resolution follows the C3 linearization (MRO) algorithm, computed once at class creation in $O(n)$ where $n$ is the inheritance chain length.

Instance attributes live in self.__dict__ — one dict per object. Class attributes live in ClassName.__dict__ — shared by all instances. Attribute lookup follows the descriptor protocol: Python first checks the class hierarchy (via MRO) for data descriptors, then the instance __dict__, then the class hierarchy for non-data descriptors. This lookup is $O(d)$ where $d$ is the MRO depth, but CPython caches method lookups via version tags on the type object, making repeated access effectively $O(1)$. Accidentally shadowing a class attribute with self.x = ... creates a new instance attribute that hides the class one.

Dunder methods hook into CPython's internal slots — __add__ maps to tp_as_number->nb_add, __len__ maps to tp_as_sequence->sq_length. These are resolved at the type level, not the instance level, so type(obj).__add__ is called rather than obj.__add__. This is why you cannot override dunders on a per-instance basis. __repr__ should produce an unambiguous string (ideally valid Python), while __str__ is for human-readable output. __hash__ must satisfy: if $a == b$ then $\text{hash}(a) == \text{hash}(b)$. Objects that define __eq__ without __hash__ become unhashable (cannot be dict keys).

Python uses multiple inheritance with the C3 linearization algorithm (MRO) to resolve method lookup order. For a class hierarchy with $n$ classes, the MRO is computed in $O(n^2)$ worst-case at class creation time. super() follows the MRO, not just the immediate parent — in diamond inheritance D(B, C) where B(A) and C(A), super() in B calls C's method, not A's. isinstance(obj, cls) checks the MRO chain in $O(d)$ where $d$ is the depth. Abstract base classes (abc.ABC) enforce interface contracts: @abstractmethod prevents instantiation if the method is not overridden, catching errors at construction time rather than at call time.

The init/fit/predict pattern separates hyperparameters (set at construction, $O(1)$) from learned parameters (computed during fit(), typically $O(n \cdot d)$ for $n$ samples and $d$ features). This separation enables: (1) cloning unfitted estimators with sklearn.base.clone() which copies __init__ args but not fitted state, (2) grid search over hyperparameters by creating many clones, and (3) serialization of trained models via pickle or joblib. The fit() method returns self to enable method chaining: model.fit(X, y).predict(X_new). Fitted attributes use a trailing underscore convention (coef_, intercept_) to distinguish them from hyperparameters.

NumPy vectorization replaces Python's interpreter loop with compiled C loops over contiguous memory. A Python for loop processes one element per $\sim 50$ns (bytecode dispatch, type checking, boxing). A NumPy vectorized operation processes one element per $\sim 1$–5ns using SIMD instructions (SSE/AVX) that operate on 4–8 floats simultaneously. For $n$ elements, the speedup is roughly $10$–$100\times$. Matrix multiplication $\mathbf{y} = \mathbf{X}\mathbf{w}$ with $\mathbf{X} \in \mathbb{R}^{n \times d}$ costs $O(nd)$ FLOPs — NumPy delegates to BLAS libraries (OpenBLAS, MKL) that achieve near-peak hardware throughput via cache-blocking and vectorized kernels.

Broadcasting eliminates explicit data replication by virtually expanding arrays during element-wise operations. Rules: align shapes from the right; dimensions of size $1$ stretch to match the other array. $\mathbf{X} - \boldsymbol{\mu}$ with $\mathbf{X} \in \mathbb{R}^{n \times d}$ and $\boldsymbol{\mu} \in \mathbb{R}^{d}$ subtracts each column's mean without copying $\boldsymbol{\mu}$ $n$ times — the actual memory used is $O(nd)$ for the output, not $O(nd) + O(nd)$. Broadcasting is valid when, for each dimension, sizes are either equal or one of them is $1$. Incompatible shapes raise ValueError. Outer products are a broadcasting pattern: a[:, None] * b[None, :] computes $a_i \cdot b_j$ for all $i, j$.

Exploratory data analysis (EDA) before modeling prevents garbage-in, garbage-out. df.info() runs in $O(n \cdot d)$ to compute non-null counts per column. df.describe() computes $O(n)$ statistics (mean, std, quartiles) for each numeric column using a single pass with Welford's online algorithm for numerically stable variance. Missing value patterns matter: MCAR (missing completely at random) can be safely dropped, MAR (missing at random) can be imputed, and MNAR (missing not at random) requires domain knowledge. Class imbalance detection via value_counts() is $O(n)$ and critical — a 99:1 imbalance means a dummy classifier achieves $99\%$ accuracy.

A float64 array of $n$ elements uses exactly $8n$ bytes of contiguous memory plus a small header ($\sim 112$ bytes). Downcasting to float32 halves memory to $4n$ bytes with $\sim 7$ significant digits of precision — sufficient for most ML since gradient noise exceeds float32 precision loss. Pandas Categorical dtype stores $k$ unique values once plus an integer index per row: memory is $O(k \cdot L + n \cdot \lceil\log_2 k\rceil / 8)$ vs $O(n \cdot L)$ for strings of average length $L$. Chunked loading with pd.read_csv(chunksize=m) processes $m$ rows at a time using $O(m \cdot d)$ memory, enabling processing of files larger than RAM in a streaming fashion.

The Estimator API enforces a consistent interface: fit(X, y) learns model parameters from training data, predict(X) applies the learned mapping. For linear models, fit() solves $\min_w \|Xw - y\|^2$ in $O(nd^2)$ via the normal equations or $O(ndk)$ via $k$ iterations of gradient descent. For tree-based models, fit() is $O(n d \log n)$ per tree. The score() method computes accuracy (classification) or $R^2$ (regression) in $O(n)$. get_params()/set_params() enable programmatic hyperparameter access — the foundation of GridSearchCV which evaluates $\prod_i |\text{grid}_i|$ parameter combinations.

Transformers follow the fit/transform pattern: fit(X) learns statistics in $O(n \cdot d)$ (e.g., StandardScaler computes $\mu_j = \frac{1}{n}\sum_i x_{ij}$ and $\sigma_j = \sqrt{\frac{1}{n}\sum_i (x_{ij} - \mu_j)^2}$ per feature), and transform(X) applies $z_{ij} = (x_{ij} - \mu_j) / \sigma_j$ in $O(nd)$. fit_transform(X) combines both in a single pass when possible. The critical rule — fit on train only — prevents data leakage: if test statistics inform the transformation, the model indirectly "sees" test data, inflating evaluation metrics. MinMaxScaler maps to $[0, 1]$ via $(x - x_{\min}) / (x_{\max} - x_{\min})$.

A Pipeline chains $k$ transformers and a final estimator. pipe.fit(X, y) calls fit_transform() on each transformer sequentially, passing the output as input to the next stage — total complexity is $\sum_{i=1}^{k-1} O(f_i) + O(f_k)$ where $f_i$ is the cost of stage $i$. During cross-validation, the pipeline refits all transformers on each fold's training set, preventing information leakage across folds. pipe.predict(X) calls transform() (not fit_transform()) on each transformer, then predict() on the final estimator. Pipeline exposes nested parameters via __ notation: pipe.set_params(model__C=0.1) sets the regularization parameter of the model step.