Chapter 1: Python Foundations

Python variables are pointers stored on the stack, each holding a reference (memory address) to a heap-allocated object. Assignment a = b copies the 8-byte pointer, not the object — $O(1)$ regardless of object size. The id() function returns this address. Reference counting tracks how many pointers target each object; when the count hits zero, the object is freed. Circular references require the cyclic garbage collector, which runs in $O(n)$ where $n$ is the number of objects in the cycle.

Python int uses arbitrary-precision arithmetic: internally it stores an array of 30-bit "digits," so a $k$-bit integer uses $\lceil k/30 \rceil$ machine words. Addition is $O(k)$, multiplication uses Karatsuba's algorithm at $O(k^{\log_2 3}) \approx O(k^{1.585})$. Floats are IEEE 754 double-precision: 1 sign bit, 11 exponent bits, 52 mantissa bits, giving $\approx 15$–16 significant decimal digits and a range up to $\sim 1.8 \times 10^{308}$. The classic $0.1 + 0.2 \neq 0.3$ arises because $0.1$ has no exact binary fraction representation.

Python strings are immutable arrays of Unicode code points stored as compact arrays (Latin-1, UCS-2, or UCS-4 depending on the widest character). Indexing is $O(1)$ since each character occupies a fixed number of bytes within its encoding. Concatenating $n$ strings with + in a loop is $O(n^2)$ total because each concatenation copies all previous characters into a new allocation. Use ''.join(parts) for $O(n)$ concatenation. String hashing uses SipHash, computed lazily and cached — so using a string as a dict key is $O(L)$ on first use but $O(1)$ thereafter, where $L$ is the string length.

bool is a subclass of int in Python: True == 1 and False == 0, so booleans participate directly in arithmetic. None is a singleton — there is exactly one None object in the interpreter, which is why is None (pointer comparison, $O(1)$) is preferred over == None (which invokes __eq__, potentially $O(n)$ for custom types). Truthiness evaluation calls __bool__() first, then __len__() as a fallback; NumPy arrays deliberately raise ValueError on __bool__ when they contain more than one element to prevent ambiguous truth testing.

Type annotations are stored in __annotations__ dictionaries at function and module level but have zero runtime cost — CPython ignores them during execution. Static analyzers like mypy perform Hindley-Milner-style type inference extended with gradual typing: annotated code is checked at $O(n)$ in the size of the AST, while unannotated functions are treated as Any. Generic types like list[int] use parametric polymorphism, and TypeVar enables bounded quantification: T = TypeVar('T', bound=Comparable) restricts $T$ to types with ordering.

Immutable objects can be safely shared across references because no mutation is possible — this is why Python interns small integers ($-5$ to $256$) and short strings, reusing the same object for identical values. Mutable objects like lists use a dynamic array internally: append() is amortized $O(1)$ because the array doubles capacity when full ($1, 4, 8, 16, 25, 35, ...$), giving a geometric growth pattern. Copying a list with a.copy() is $O(n)$ — it copies the pointer array but not the underlying elements (shallow copy). copy.deepcopy() recursively copies all nested objects at $O(N)$ where $N$ is the total object graph size.