Time Complexity, Data Structures, and OOP for ML Systems

10.1 Time Complexity and Big O Notation

10.1.1 Symbol Registry — Time Complexity

• $N$ — input size: number of data samples or number of features — integer ≥ 1
• $O(\cdot )$ — Big O notation: asymptotic upper bound on operations as a function of input size
• $O(1)$ — constant time: operations do not grow with input size
• $O(\log N)$ — logarithmic time: operations grow as the logarithm of input size
• $O(N)$ — linear time: operations grow proportionally with input size
• $O(N\log N)$ — linearithmic time
• $O(N^2)$ — quadratic time: operations grow as the square of input size
• ${\log }_{2}N$ — base-2 logarithm: number of times $N$ can be divided by 2 to reach 1

10.1.2 Why Time Complexity Matters in ML

When you write ML code, you need a way to measure how long your algorithm takes to run. You cannot simply clock it once and call it done. The real question: how does running time grow as data grows?

Take a dataset with 100 records. The algorithm runs fast. Now increase to 1,000 rows. Then to 1 million, 1 billion, 1 trillion rows. Does the time stay roughly constant? Does it grow linearly? Does it explode? When you work with millions of records and billions of parameters. An algorithm that works on a small dataset may fail at scale. You must make adjustments.

The primary tool for answering this question is Big O notation. As Ned Batchelder put it: Big O is how code slows as data grows.

The paper-folding analogy. Take a sheet of paper and fold it in half. Fold again. And again. After just 10 folds, the thickness multiplies by $2^{10}=1024$. After 20 folds, it crosses a million layers. Now reverse the question: if your paper has $N$ layers, how many times did you fold it? That is ${\log }_{2}N$. Logarithmic time works the same way — every step halves your remaining work, so even enormous inputs collapse quickly. The analogy breaks when $N$ is not a power of 2, but the scaling behavior holds.

10.1.3 What Big O Notation Means

Big O notation measures the order of an algorithm — how the number of operations scales with input size.

• O stands for order of the function.
• N represents the number of data samples (100 rows, 1,000 rows, 1 million rows…).
• N can also represent the number of features (10 features, 50 features, etc.).
• In ML, you use Big O for both training time and inference time. Inference (read/search) time is the dominant concern.

There are also small-o, Theta, and Omega notations, but Big O is the one that matters for practical ML work. Out of the entire family, only four complexities show up in ML algorithms. These are $O(1)$, $O(\log N)$, $O(N)$, and sometimes $O(N\log N)$. You hardly ever need $O(N^2)$ or $O(N!)$ in ML contexts. The travelling salesman problem is one of the few places $O(N!)$ appears.

Classification as grades:

• $O(1)$ — A grade. Best retrieval time. Constant time, regardless of input size.
• $O(\log N)$ — B grade. Half the time compared to linear, but still more than constant.
• $O(N)$ — C grade. Linear time; time grows proportionally with input.
• $O(N\log N)$ — D grade.
• $O(N^2)$ and worse — progressively lower grades.

10.1.4 Logarithm Fundamentals

10.1.5 The Big O Complexities in Detail

$O(1)$ — Constant Time

Random access of an element in an array is $O(1)$. The time does not depend on the size of the array at all. Inserting at the beginning of a linked list is also $O(1)$. Dictionary key lookup in Python — finding a value by its key — is $O(1)$ on average. This is the gold standard for retrieval.

$O(\log N)$ — Logarithmic Time

Binary search is the classic example. Each step discards half the remaining search space. Think of searching for a contact named "Shreyas" in your phone. Names are arranged alphabetically. First split A–M and N–Z. The name falls in N–Z, so discard A–M. Then split N–R and R–Z. The name is in R–Z. Keep halving until you find the contact. The number of steps is $O(\log N)$.

$O(N)$ — Linear Time

Linear search checks every item. If you have 1,000 items and the target is the 1,000th, you go through all of them. A single pass through a dataset — computing the mean, finding the maximum, normalizing features — is $O(N)$.

$O(N\log N)$

Less common in basic ML operations but essential for sorting. Merge sort and quicksort both run in $O(N\log N)$. This arises when you repeatedly split data into halves ($\log N$ levels) and process each element at every level ($N$ operations per level).

10.1.6 Worst-Case vs Best-Case Analysis

10.1.7 Why ML Focuses on Read/Search, Not Insert/Update

Another reason: training is a one-time cost (or periodic retraining), amortized across millions of inferences. Inference happens on every single query. If inference is $O(N)$ on a billion-record index, your product is dead on arrival.

10.1.8 Comparison Table: When to Choose Which

10.1.9 Visual Intuition: Growth Curves

Imagine a chart with $N$ on the horizontal axis, ranging from 1 to 1,000,000. The vertical axis shows number of operations, on a scale from 0 to 1,000,000.

• $O(1)$ is a flat horizontal line hugging the bottom — no matter how far right you go, it never rises. It is the pavement, not a curve.
• $O(\log N)$ starts slightly above $O(1)$, rises gently, and by $N=1,000,000$ reaches only about 20 operations. It looks almost flat to the naked eye.
• $O(N)$ is a straight diagonal line from origin to top-right — one-to-one growth. At $N=1,000,000$, it hits 1,000,000 operations.
• $O(N\log N)$ sits between $O(N)$ and $O(N^2)$, pulling away from the linear line as $N$ grows.
• $O(N^2)$ is a steep parabola. At $N=1,000,000$, it reaches a trillion operations — it shoots off the chart.

Takeaway: For large $N$, the gap between $O(\log N)$ and $O(N)$ is dramatic. A billion-item binary search finishes in ~30 steps; a billion-item linear scan takes ~500 million steps on average. That is the power of logarithmic growth.

10.1.10 Mathematical Recapitulation

The measure of steps for $O(\log N)$:

• $N=8$ → ${\log }_{2}8=3$ operations
• $N=16$ → ${\log }_{2}16=4$ operations
• $N=1000$ → ${\log }_{2}1000\approx 10$ operations (since $2^{10}=1024$)

In $O(N)$, the number of operations equals the number of items. In $O(\log N)$, you discard half the items at every step, so operations grow much more slowly than the input.

10.1.11 Real-World Domain Connection

Big O thinking shapes every production ML system. When you design a retrieval pipeline — say, a RAG (Retrieval-Augmented Generation) system — you must index millions of documents. A brute-force $O(N)$ cosine-similarity search against every document is not viable. Industry-standard solutions like FAISS and Annoy use approximate nearest-neighbor algorithms that run in $O(\log N)$ or even sub-logarithmic time. The same principle applies to recommendation systems (finding top-K items for millions of users), search engines (ranking billions of pages). Vector databases (semantic search over embeddings). Understanding complexity classes lets you pick the right data structure — hash tables for $O(1)$ lookup. B-trees for $O(\log N)$ range queries. Approximate methods when exact results are not required. Every time you open a Jupyter notebook and import sklearn. The underlying algorithms have complexity guarantees that make them usable at scale.

10.2 Data Structures — Foundational Overview

Before diving into Python-specific data structures, it helps to understand the general landscape of data structures used across computer science. Not all of these are needed day-to-day in ML. But the concepts — especially trees — appear in software engineering. They connect to ML systems.

10.2.1 What Is a Data Structure?

A data structure is a container that holds data in a specific organization so you can store and retrieve it efficiently. Data comes in multiple formats — numeric, string, binary — and you need the right structure for each use case.

Data structures split into two broad categories:

• Built-in / basic: arrays, stacks, queues, linked lists
• Advanced: trees, hash tables, graphs (many of which are built on top of the basics)

10.2.2 Array

An array is a collection of homogeneous elements stored in contiguous memory. A typical array might hold [10, 20, 30, 40] (all numbers) or a fruits array ["apple", "banana", "orange"] (all strings). Numbers can include decimals — 30.5, 45.7, etc.

This is a language-agnostic concept. Python lists and NumPy arrays are both built on the array idea.

10.2.3 Stack — Last In, First Out (LIFO)

Imagine a stack of 10 plates at home. You place the first plate, then the second on top, then the third. When you want to retrieve a plate, you always take the topmost one — the last one you placed. This is LIFO: Last In, First Out.

Two operations define a stack:

• Push: add an element to the top — O(1)
• Pop: remove the topmost element — O(1)

Stacks appear everywhere in computing. Your browser's back button is a stack — each page you visit is pushed on top. Pressing back pops the top page. The undo feature in any text editor is a stack of actions. Function calls in every programming language use a call stack — each function call pushes a frame, each return pops it. Recursion works because of the call stack.

10.2.4 Queue — First In, First Out (FIFO)

Think of a movie ticket queue. The person who arrives first gets the first ticket. The second person gets the second ticket. This is FIFO: First In, First Out.

Two operations define a queue:

• Enqueue: add an element to the back
• Dequeue: remove an element from the front

Real-world queues include printer queues (first document sent prints first), message queues in distributed systems. Request queues in web servers. In ML systems, inference requests arriving at a model server are typically queued and processed in FIFO order.

10.2.5 Linked List

A linked list stores each element in a node. A node contains:

1. The data element itself
2. A left pointer (to the previous node, in doubly-linked lists)
3. A right pointer (to the next node)

Example: Storing [10, 20, 30] in a singly linked list:

• Node 1: data = 10, no left pointer, right pointer → Node 2
• Node 2: data = 20, left pointer → Node 1, right pointer → Node 3
• Node 3: data = 30, left pointer → Node 2, no right pointer

A doubly linked list has pointers in both directions — each node knows both its predecessor and its successor. A circular linked list connects the last node back to the first.

10.2.6 Tree Data Structure

A tree has a root node at the top and child nodes branching downward. The nodes at the very bottom are called leaves — they have no children of their own.

A real-world analogy: your Windows file system. The C: drive is the root. Inside it are folders (child nodes). Within those folders are subfolders or files (leaves). If every parent has at most two children, the structure is called a binary tree.

Tree structures appear throughout software engineering. An XML document forms a tree — the root element contains child elements, which can themselves contain further children. The HTML DOM (Document Object Model) is also a tree, and web applications routinely use tree traversal algorithms.

10.2.7 Tree Traversal — DFS and BFS

When you search for a file on your C: drive, the operating system must walk the tree. Two strategies exist.

#### Purpose

Tree traversal means visiting every node in a tree exactly once. The order of visits depends on the strategy. DFS and BFS are the two fundamental approaches. They apply to trees and graphs alike.

#### Inputs and Outputs

• Input: A tree (or graph) with a designated root node.
• Output: An ordered sequence of all nodes, determined by the traversal rule.

DFS and BFS produce different orderings from the same tree. Neither is universally "better" — the right choice depends on your goal.

#### Steps — Depth-First Search (DFS)

DFS dives deep before exploring siblings.

1. Start at the root node.
2. Visit the node.
3. Recursively traverse the leftmost unvisited child, then its leftmost child, and so on until you hit a leaf.
4. Backtrack to the last node that still has unvisited children.
5. Repeat from step 2 until every node is visited.

DFS uses a stack — either the call stack (recursion) or an explicit LIFO structure.

#### Steps — Breadth-First Search (BFS)

BFS explores level by level.

1. Start at the root node. Enqueue it.
2. Dequeue a node. Visit it.
3. Enqueue all its immediate children (left to right).
4. Repeat from step 2 until the queue is empty.

BFS uses a queue — the FIFO structure from Section 10.2.4.

#### Worked Trace — DFS vs BFS

Consider this small tree:

A
/ \
B   C
/ \   \
D   E   F

DFS (pre-order):

1. Start at A → visit A
2. Go to left child B → visit B
3. Go to left child D → visit D
4. D is a leaf. Backtrack to B. Go to right child E → visit E
5. E is a leaf. Backtrack to B (done). Backtrack to A.
6. Go to right child C → visit C
7. Go to right child F → visit F
8. Done.

DFS order: A → B → D → E → C → F

BFS:

1. Enqueue A. Queue: [A]
2. Dequeue A, visit A. Enqueue B, C. Queue: [B, C]
3. Dequeue B, visit B. Enqueue D, E. Queue: [C, D, E]
4. Dequeue C, visit C. Enqueue F. Queue: [D, E, F]
5. Dequeue D, visit D. No children. Queue: [E, F]
6. Dequeue E, visit E. No children. Queue: [F]
7. Dequeue F, visit F. No children. Queue: empty.
8. Done.

BFS order: A → B → C → D → E → F

#### When to Use Which

DFS is more memory-efficient for deep, narrow trees. BFS is better when you expect the answer close to the root. Both appear in ML systems — DFS for tree-based model inference, BFS for graph-based recommendation algorithms and nearest-neighbor search.

10.2.8 Connecting General Data Structures to ML

These general data structures are not part of a typical ML curriculum, but they form the foundation of software engineering. When you build web applications, the DOM is a tree. The same concepts carry over to ML systems. Understanding the data structures helps you choose the right one. It also helps you reason about performance.

if feature_name in my_list:   # O(N) — scans every element

if feature_name in my_dict:   # O(1) — hash and jump

10.3 Python List in ML Systems

10.3.1 Symbol Registry — Python List

Think of a Python list like the row of apartment mailboxes in your building lobby. Each mailbox has a number painted on the front, and once you know that number, you walk straight to it. The number of mailboxes in the wall does not change how long it takes you to find mailbox 47. That is the superpower of lists — and the entire reason they dominate ML pipelines.

• O(1) — constant-time index access on a list
• O(N) — linear-time search through an unsorted list
• O(log N) — logarithmic-time binary search on a sorted list
• lst[i] — zero-based index access to element at position i
• lst[-1] — access to the last element

10.3.2 Definition

A Python list is a dynamic, mutable array. Mutable means changeable — you can add elements, remove elements, or modify existing elements at any time. The word comes from "mutation" — like a virus mutating, the structure can change.

Lists are written with square brackets:

lst = [100, "mango", 50.99, True]

Elements can be of different types — integer, string, float, boolean — all in one list. Python uses zero-based indexing: lst[0] is the first element, lst[1] is the second, and so on.

Because the list is mutable, you can reassign any element:

lst = [100, "mango", 50.99, True]
lst[2] = 40.66        # third element changes from 50.99 to 40.66

You can iterate with a for loop:

for element in lst:
print(element)

How contiguous memory works. Under the hood, a Python list stores elements in a single, unbroken block of RAM. Imagine a long shelf where each slot holds a reference to one of your objects. The shelf itself is one physical piece of wood — all slots are adjacent. When Python creates lst = [100, "mango", 50.99], it reserves a contiguous chunk of memory. The list variable lst stores a pointer to the start of that chunk. To find the third element, Python computes start_address + (index * element_size) and jumps straight there. That arithmetic takes the same number of CPU cycles regardless of whether the list has three elements or three million.

Because Python lists store references to objects rather than the objects themselves, each slot is the same fixed width. Typically 8 bytes on a 64-bit machine. This fixed stride is what makes the address arithmetic work. When you write lst[2], Python multiplies 2 by 8, adds the base address, reads the pointer. Follows it to the actual integer or string object.

Dynamic resizing. A Python list is not a static array. It is dynamic — it grows when you append beyond its current capacity. Internally, lists over-allocate memory. When you create an empty list, Python reserves space for a few elements. As you append, the list fills up. When it runs out of reserved slots, Python allocates a new, larger contiguous block, copies all existing references over. Frees the old block. This copy operation takes O(N) time. It happens infrequently enough that the amortized cost of a single append remains O(1). If you know the final size ahead of time, pre-allocate with [None] * n to avoid repeated copies.

10.3.3 Time Complexity: O(1) Indexing

The critical property of lists for ML: random access by index is $O(1)$. Whether your list has one element, a thousand elements, a million. A billion — lst[i] always returns in constant time. The CPU performs a single memory address calculation and follows a pointer. No loops. No searching. One arithmetic operation.

If you do not know the index and must search for a value, the time becomes $O(N)$. If the data is sorted, binary search gives $O(\log N)$.

import timeit
import statistics

def measure_lookup_time(list_size, number=1_000_000, repeat=5):
"""Measures avg time for lst[-1] lookup in nanoseconds."""
setup = f"lst = list(range({list_size}))"
stmt = "lst[-1]"
timings = timeit.repeat(stmt, setup, number=number, repeat=repeat)
single_lookup_times = [t / number for t in timings]
avg_ns = statistics.mean(single_lookup_times) * 1e9
std_ns = statistics.stdev(single_lookup_times) * 1e9
return avg_ns, std_ns

sizes = [10, 10_000, 1_000_000]
for size in sizes:
avg, std = measure_lookup_time(size)
print(f"List size {size:>9}: {avg:.2f} ns ± {std:.2f} ns")

10.3.4 Scope: When Lists Are Slow

O(1) indexing is a superpower, but it is not the whole story. Several common list operations are not constant time, and you need to recognize them in your ML code.

Inserting in the middle is O(N). If you call lst.insert(0, value) to put an element at the front. Python must shift every existing element one position to the right to make room. For a list of one million elements. That is one million copy operations — every single time you insert at the front. The same penalty applies to lst.pop(0) and del lst[0], which must shift all remaining elements left to fill the gap. If you need fast insertions and deletions at both ends, reach for collections.deque. It provides O(1) append and pop from either side.

Searching an unsorted list is O(N). When you write if "mango" in lst. Python must check each element one by one from the beginning until it either finds a match or exhausts the list. For a million-element list, that could mean a million comparisons in the worst case. If your data is sorted. Use bisect for O(log N) binary search — but note that sorting itself costs O(N log N). Sort once and search many times.

Removing a specific value is O(N). Calling lst.remove(value) first searches for the value linearly. O(N). And then shifts all trailing elements left — another O(N). It is effectively a combined search-and-delete operation, both of which scale with list size.

Appending is amortized O(1). Occasional spikes. Most lst.append(x) calls are constant time. When the internal array fills up, Python must allocate a new, larger block and copy everything. That occasional copy costs O(N). In tight loops over large datasets, these spikes can cause noticeable latency. Pre-allocate with [] * n or use list comprehensions to avoid repeated resizing.

10.3.5 Pitfalls

Pitfall 1: Mutation surprises with aliases. When you write b = a where a is a list. You are not creating a copy. You are creating a second name that points to the same list in memory. Modify b and a changes too:

a = [1, 2, 3]
b = a
b.append(4)
print(a)   # [1, 2, 3, 4]  — surprised?

Use b = a.copy() or b = a[:] to create a shallow copy. Be aware that a shallow copy duplicates the outer list but shares the inner objects. If your list contains mutable objects like other lists or dictionaries. Changes to those inner objects will still propagate across both copies.

Pitfall 2: Building lists with repeated append inside a loop. Every append call involves a function dispatch and, occasionally, an array resize. This pattern is both slow and hard to read:

result = []
for x in data:
result.append(process(x))

Replace it with a list comprehension, which runs at C speed inside the Python interpreter and avoids repeated method lookups:

result = [process(x) for x in data]

List comprehensions also pre-allocate the output list in a single pass where possible, eliminating the repeated resize overhead.

Pitfall 3: the star operator for nested lists. Writing matrix = [[0] 5] 3 creates three references to the same inner list. This does not produce three independent rows. Change one row and all three change:

matrix = [[0] * 5] * 3
matrix[0][2] = 7
print(matrix)   # [[0, 0, 7, 0, 0], [0, 0, 7, 0, 0], [0, 0, 7, 0, 0]]

Use a list comprehension instead: matrix = [[0] * 5 for _ in range(3)].

Pitfall 4: Modifying a list while iterating over it. Removing elements during iteration skips items. The indices shift as the list shrinks. Iterate over a copy. for x in lst[:] — or build a new list with only the elements you want to keep. The latter is usually cleaner and easier to reason about.

10.3.6 Why Lists Matter in ML

When you load a dataset. Say the Pima Indian Diabetes dataset — you have rows of patients. Each with features like age, BMI, glucose level, and outcome. To access the gender of the fiftieth patient, you index row 50 and the gender column. That access is O(1). One step, constant time, regardless of whether the dataset has a hundred rows or a hundred thousand.

If you need to find a specific patient by name and names are unsorted. You iterate through all N rows — O(N). Sort them alphabetically and use binary search — O(log N). The choice of data structure and pre-processing directly determines how your pipeline scales.

10.3.7 Recap and Bridge to Tuples

A Python list gives you O(1) random access by index, thanks to contiguous memory. Appending is fast on average but copies the entire array periodically. Inserting or deleting in the middle is O(N) because everything shifts. Search is O(N) on unsorted data and O(log N) on sorted data. Avoid repeated append in loops by using list comprehensions. Watch out for alias surprises — use .copy() when you need independence.

But what if you want O(1) indexing without mutability? What if you need a guarantee that your data will never change after creation? That is where tuples come in. We will look at tuples next — a close cousin of lists that trades flexibility for safety and speed.

10.4 Python Tuple in ML Systems

10.4.1 Symbol Registry — Python Tuple

What if you need a list that nobody can accidentally change — not you. Not your teammate, not a future dependency bump? Enter the tuple. It is the museum exhibit of data structures.

Think of a museum exhibit behind glass. You can look at the artifact all you want. You can read the placard, count the details, inspect it from every angle. But you cannot touch it, you cannot move it, and you certainly cannot take a Sharpie to it. That is exactly how a Python tuple works: full access for reading, zero permission for writing. The immutability is not a suggestion — it is enforced by the language runtime.

• tup = (10, 20, 30) — tuple literal with parentheses
• tup[i] — O(1) index access, just like a list
• Immutable — no append(), no insert(), no pop(), no del, no index assignment
• Hashable — can be used as dictionary keys and set members
• Static array — no over-allocation, no resizing logic, simpler memory representation

10.4.2 Definition and Memory Layout

A Python tuple is an immutable, static array. Once created, the collection is frozen. You cannot add elements, remove elements, or change existing elements. The word immutable means "not mutable" — incapable of mutation.

Tuples are written with parentheses:

tup = (10, 20, 30)

Like lists, they can hold mixed types — integer, string, float, boolean — all in one tuple. Indexing works the same way: tup[0] is 10, tup[1] is 20, tup[2] is 30. Negative indices work too: tup[-1] gives 30.

Static array internals. Under the hood, a tuple allocates exactly the memory it needs and never grows. Unlike a list, which deliberately over-allocates extra slots to accommodate future appends. A tuple reserves space for precisely its N elements. No spare capacity. No resize logic. No copy-on-grow overhead. This makes the tuple's internal C struct simpler and its creation marginally cheaper than an equivalent list.

Because the tuple is immutable, the Python runtime can make assumptions that are impossible for lists. The interpreter knows the size will never change, so it can skip boundary checks and resize overhead entirely during access. More importantly, the runtime can cache and reuse small tuples. When Python encounters a tuple like (1, 2, 3) in source code, the compiler sometimes interns it. Storing one canonical copy and reusing it — because immutability guarantees the value will never change. Lists can never benefit from this optimization because their contents are unpredictable at compile time.

These two facts — static allocation plus runtime caching — make tuple access slightly faster than list access in practice. Even though both are O(1). The difference is typically a few nanoseconds, invisible in isolation but meaningful inside tight loops over millions of iterations.

Tuples also pair well with application-level caching. If you have precomputed results you want to memoize, storing them as tuples gives you an extra guarantee. No downstream code can accidentally mutate your cache entries.

10.4.3 When to Use Tuples in ML

Tuples are the right choice when you need to store something that should never change after it is created:

• Dataset shape. X.shape returns a tuple like (150, 4). Once you read the data, the shape is fixed. The number of rows and columns is a property of the loaded dataset, not something you modify on the fly. A tuple communicates this intent: "this value describes what is, not what could be."

• Hyperparameters and dropout rates. Values set once before training — learning_rate = 0.001. dropout = 0.5 — are natural tuples. You never modify them during a training run. If you do need a different value, you create a new tuple for the next experiment.

• Dataset properties and dimensions. Anything that describes the data rather than constituting the data itself: df.shape, df.columns, image.size. These are read-only descriptors.

• Return values from functions. Multiple return values in Python are packed into a tuple. return x. Y, z is actually return (x, y, z). Unpacking — a, b, c = func() — is tuple unpacking.

• Dictionary keys and set members. Because tuples are hashable (provided their contents are hashable). They can serve as keys in dictionaries and members of sets. If you need a compound key — say, a coordinate pair (row, col) — a tuple is the natural choice. A list would raise TypeError: unhashable type: 'list'.

10.4.4 Time Complexity: O(1) Access

Tuple indexing is O(1) — constant time, just like lists. The address arithmetic is identical: base address plus index times element size. Since tuples are static arrays without over-allocation. The stride between elements is the same fixed width of a reference pointer (8 bytes on 64-bit machines).

import timeit
import statistics

def measure_tuple_lookup(size, number=1_000_000, repeat=5):
setup = f"tup = tuple(range({size}))"
stmt = "tup[-1]"
timings = timeit.repeat(stmt, setup, number=number, repeat=repeat)
single_lookup_times = [t / number for t in timings]
avg_ns = statistics.mean(single_lookup_times) * 1e9
std_ns = statistics.stdev(single_lookup_times) * 1e9
return avg_ns, std_ns

sizes = [10, 10_000, 1_000_000]
for size in sizes:
avg, std = measure_tuple_lookup(size)
print(f"Tuple size {size:>9}: {avg:.2f} ns ± {std:.2f} ns")

10.4.5 Scope: When Tuples Win and When They Lose

Where tuples win:

• Absolute immutability guarantees. If you pass a tuple to a function, you know with certainty that no callee. Not even a malicious one — can modify its contents. With a list, you only have convention and trust.

• Hashability. Tuples can be dictionary keys and set members. This unlocks patterns like memoization caches keyed by parameter tuples, coordinate lookup tables, and deduplication via sets.

• Marginal speed advantage. The runtime's ability to intern tuples and skip mutation checks gives tuples a slight edge. In code paths that are executed millions of times. Like inner loops of data pipelines — those few nanoseconds per access accumulate.

• Semantic intent. Using a tuple signals to readers. "this collection is meant to be read, not written." A list says the opposite. Code that communicates its intent is easier to maintain.

Where tuples lose:

• You need to grow the collection. If you are accumulating results during a training loop. Appending each epoch's loss to a history — a tuple is useless. Every append would require creating an entirely new tuple and copying all existing elements, which is O(N) per operation.

• You need to modify elements in place. If you are normalizing a feature column row by row, you need mutability. Tuples force you to create new objects for every change, which is both slow and wasteful of memory.

• You need insertion or deletion at arbitrary positions. Tuples have no insert(), no pop(), no remove(). To "delete" the third element, you must slice: tup[:2] + tup[3:]. That creates two intermediate copies and a final concatenated tuple — O(N) time and O(N) memory.

• You are building the collection incrementally from unknown data. If you do not know the size ahead of time. Say, loading unknown-length data from a file — a list with append is amortized O(1). A tuple requires reading everything into a list first, then converting.

10.4.6 Tuple vs List Comparison

The performance difference in raw index access is negligible — both are O(1) within a few nanoseconds. The choice between tuple and list is almost never about speed. It is about contract. A tuple promises immutability. A list promises flexibility. Choose the one that matches what you want the code to guarantee.

10.4.7 Pitfalls

Pitfall 1: The single-element tuple trap. This is the most common tuple mistake in Python and it bites even experienced developers:

not_a_tuple = (42)
print(type(not_a_tuple))   # <class 'int'>  — surprise!

actually_a_tuple = (42,)
print(type(actually_a_tuple))   # <class 'tuple'>

Python interprets (42) as the integer 42 wrapped in grouping parentheses, not as a tuple. The trailing comma — (42,) — is what tells the parser this is a tuple with one element. Without the comma, the parentheses are just mathematical grouping symbols.

This matters in ML contexts. If you are building a configuration tuple dynamically and sometimes end up with a single value. Code like dims = (batch_size,) is correct while dims = (batch_size) is silently wrong.

Pitfall 2: Thinking tuples are always faster than lists. The speed difference is real but microscopic — a few nanoseconds per access. In practice, the overhead of Python's dynamic dispatch, garbage collection, and function call machinery dwarfs the difference. Do not rewrite your list-based pipeline to tuples expecting a measurable speedup. The real wins from tuples are correctness (immutability guarantees) and hashability — not raw performance.

Pitfall 3: Mutable elements inside immutable tuples. A tuple is immutable, but the objects it references are not protected:

tup = ([1, 2], [3, 4])
tup[0].append(99)
print(tup)   # ([1, 2, 99], [3, 4])  — the tuple "changed"!

tup[0] = [5, 6]   # TypeError: 'tuple' object does not support item assignment

The tuple prevents reassigning its slots — you cannot point tup[0] to a different list. But the object at tup[0] is itself a mutable list, and that list can change freely. The immutability guarantee applies only to the tuple's references, not to the payload.

This is dangerous in caching scenarios. If you cache a tuple containing a list and some code later mutates that list, your cache is silently corrupted. For truly immutable containers, ensure all elements are themselves immutable: ints, strings, tuples, frozensets.

Pitfall 4: Converting between list and tuple too often. Every conversion creates a new object and copies all references — O(N):

tup = tuple(some_list)      # copies N references
lst = list(some_tuple)      # copies N references

In a hot loop, repeated tuple() and list() calls can become a hidden quadratic cost. Convert once at the boundary where you need the other type, not inside the loop.

10.4.8 Recap and Bridge to Dictionary

A Python tuple is a static, immutable array with O(1) index access, simpler memory layout than a list. The ability to serve as a dictionary key. Use tuples when you want a guarantee — enforced by the language runtime — that your data will never change after creation. Dataset shapes, hyperparameter constants, and compound dictionary keys are the natural habitat of tuples in ML code. Remember the trailing comma for single-element tuples. Remember that immutability does not extend to mutable elements stored inside the tuple.

Both lists and tuples give you O(1) indexing, but neither gives you O(1) lookup by name. If you want to map a string. Like "learning_rate" — to a value — like 0.001 — and retrieve it in constant time without scanning. You need a different data structure. That structure is the dictionary, powered by a hash table, and it is up next.

10.5 Python Dictionary in ML Systems

Need to find a value instantly without knowing its position? That is the dictionary's superpower. Instead of searching through every item one by one (like we must with a list). A dictionary jumps directly to the right answer in a single step. No matter how large the dataset grows.

10.5.1 Symbol Registry — Python Dictionary

Think of a library's index card system. You walk in looking for a specific book by title. You do not walk down every aisle scanning shelves — you flip through the card catalog, find the title. Read the shelf number. The card catalog maps titles to locations. A Python dictionary does exactly this. It maps keys to values using a hash table that gives you the answer in constant time.

• Dictionary: a mutable collection of key-value pairs, backed by a hash table
• O(1) average-time key lookup, insertion, and deletion — constant regardless of dictionary size
• hash(key) — built-in function that produces a numeric fingerprint for any hashable key
• Key — the unique identifier in a key-value pair. Must be immutable (int, str, float, tuple — but NOT list, dict, or set)
• Value — the data stored against a key; can be anything, mutable or immutable
• Memory footprint: dictionaries carry significant overhead per entry; a dict of 10,000 items can occupy megabytes of RAM

10.5.2 Definition and Hash Table Internals

A Python dictionary is a mutable data structure that stores key-value pairs. Notation uses curly braces:

d = {"name": "John", "age": 25}

Keys must be unique — you cannot have two entries with the same key. Values can be duplicated. Keys can be integers, strings, floats, or even tuples — anything hashable, meaning anything immutable. Lists, dictionaries, and sets are not hashable and cannot serve as keys.

Sets are a close cousin of dictionaries. They use the same hash table machinery, but store only keys with no associated values. If you only need to track membership ("is this element present?"). A set is the right tool and avoids the per-entry value pointer overhead.

10.5.3 How the Hash Table Works

Dictionaries are implemented using a hash table — an array under the hood. Here is what happens internally when you store d["name"] = "John":

1. You provide the key "name".
2. Python computes a hash value — a numeric fingerprint — for that key using the built-in hash() function.
3. Python uses that hash value modulo the internal array size to compute an index.
4. The value "John" is placed at that index in the underlying array.
5. When you later look up d["name"], Python hashes "name" again, jumps to the same index, and returns "John".

No scanning. No searching. One hash computation plus one array access.

>>> hash(0)
0
>>> hash(1)
1
>>> hash(42)
42

>>> hash("name")
5666763882210910770
>>> hash("name")   # same key, same hash — every time
5666763882210910770
>>> hash("Name")   # case-sensitive — different hash
-8577181387926203852

Hash collisions: Two different keys can hash to the same array index. This is rare but inevitable with a large enough key space and small enough table. Python handles collisions through open addressing — if a slot is occupied, Python probes the next available slot. You do not need to manage this yourself. The dictionary grows its internal table when it gets too crowded (typically when it reaches about two-thirds capacity). This keeps the collision rate low and performance near O(1).

10.5.4 Time Complexity: O(1) Average

Dictionaries achieve O(1) average time for:

• Retrieval (lookup by key: d[key])
• Insertion (adding a new key-value pair: d["new"] = val)
• Deletion (removing a key-value pair: del d[key])

What "average" means: in the worst case (pathologically many hash collisions), a lookup could degrade to O(N). But Python's hash algorithm and dynamic resizing make this vanishingly unlikely in practice.

This makes dictionaries one of the fastest general-purpose data structures in Python. Every key lookup requires only the hash computation and a direct jump — no scanning, no tree traversal, no loop.

Context for other operations:

• If you need to iterate through every item in the dictionary (e.g.. for k, v in d.items()), time grows as O(N). You visit every entry.
• If you need to check membership (key in d), that is O(1) — same hash-based lookup.
• If you need to find a value without knowing its key, you must scan all values — O(N). Dictionaries are optimized for key-based access, not value-based search.
• If values happen to be sorted alphabetically, you could achieve O(log N) via binary search. Standard dictionary lookup by key is always O(1).

10.5.5 Key Mutability Clarification

d = {"name": "Alice"}
d["name"] = "Bob"      # value changes — perfectly legal

val = d.pop("name")    # remove old key, grab its value
d["full_name"] = val   # insert with new key

10.5.6 Dictionary in ML Context

Real-world ML use cases where dictionaries shine:

• Feature name to index mapping. When your dataset has feature columns like "age", "income". "city", you map each name to a numeric column index for array-based ML libraries. feature_index = {"age". 0, "income": 1, "city": 2}. Lookups are O(1) — instant regardless of feature count.

• Word-to-vector lookup. In NLP, embedding dictionaries map each word in a vocabulary to its dense vector representation. A vocabulary of 100,000 words needs fast, single-step word lookups.

• Label encoding. Mapping categorical string labels ("cat", "dog") to integer class IDs (0, 1) uses a dictionary. Both directions: label_to_id and id_to_label.

• Caching. Memoizing expensive function results: cache = {}, store results keyed by input parameters. Before recomputing, check if key in cache.

• Configuration and hyperparameters. Storing named parameters as config = {"learning_rate": 0.001, "epochs": 50}.

When dictionaries are the wrong choice:

• Memory-constrained environments. Dictionaries have a large per-entry overhead (roughly 72 bytes per entry for the hash table bookkeeping. Plus key and value objects). For millions of entries, this adds up. Consider NumPy arrays or database-backed storage instead.

• Ordered iteration. Python 3.7+ guarantees insertion order, but relying on it for algorithmic logic is fragile. If order matters, maintain a separate list of keys.

• Homogeneous numeric data. If your keys are dense integers starting from 0 and your values are all floats. A list (or NumPy array) is far more memory-efficient and still O(1).

• Range queries. Dictionaries cannot answer "give me all keys between 10 and 20" efficiently — that requires O(N) scan. Use a tree-based structure (or sort-then-bisect) for range queries.

Pitfalls to avoid:

• Using a mutable type as a key (e.g., a list) — raises TypeError: unhashable type.
• Assuming insertion order implies sorted order — it does not. {3. "a", 1: "b"} iterates as 3, 1 in Python 3.7+.
• Modifying a dictionary while iterating over it — raises RuntimeError. Iterate over a copy of keys instead.

---

Recap. A Python dictionary is a hash table that maps hashable keys to values with O(1) average lookup, insertion, and deletion. Keys must be immutable because the hash must stay fixed. Dictionaries are ideal for symbol registries, caches. Name-to-index mappings — any time you need instant access by a unique key. Their main cost is memory overhead.

Bridge to NumPy. In the next section, we move from Python's built-in data structures to NumPy arrays. The workhorse of numerical computing in ML. Where dictionaries give you O(1) by key. NumPy arrays give you O(1) by index and O(N) vectorized operations that run at compiled C speed, not Python loop speed.

10.6 NumPy Arrays in ML Systems

One import statement — import numpy as np — can make your numerical code 100 times faster. This is not an exaggeration. It is the measured, reproducible gap between native Python lists and NumPy arrays for the simplest numeric operations. The gap only widens for linear algebra, matrix multiplication, and gradient computation. If Python lists were already good enough for numerical work, the NumPy project would never have been created.

10.6.1 Intuition — Why a Rewrite in C Matters

When Python iterates over a list of numbers, every single element requires a layer of runtime machinery. The interpreter must:

• Chase a pointer to the Python object representing that number.
• Inspect the object's type tag (is it an int, a float, a str?).
• Unbox the raw numeric value.
• Perform the arithmetic operation.
• Box the result back into a new Python object.

Every element in a Python list is an independent, heap-allocated PyObject. The list itself stores only an array of pointers to those objects. Iteration so walks pointer→object→unbox→compute→box for every element. The pointer-chasing destroys CPU cache locality, and the type-checking burns cycles on every single item.

A NumPy ndarray stores raw numeric bytes in a single contiguous block of memory. The array knows one type and one size per element at creation time. There are no per-element type tags, no per-element pointers, and no per-element boxing. When you write arr + 5. NumPy calls a tight C loop that adds 5 to every element without leaving compiled code.

The ndarray header is a small struct containing:

• A pointer to the contiguous data buffer.
• The dtype (one type for all elements).
• A shape tuple (dimensions).
• A strides tuple (bytes to skip per index along each axis).

Everything else is raw bytes.

10.6.2 Formal Definition and the N-Dimensional Array

A NumPy ndarray (N-dimensional array) is a homogeneous, contiguous block of numeric values with a fixed dtype. It is the central data structure of numerical computing in Python ML.

NumPy is implemented in C. Python provides the clean []-syntax API, but all computation happens inside compiled C loops. This is the primary source of the 100—120× speedup over equivalent Python list code.

NumPy uses the same square-bracket syntax as Python lists, but with spaces as delimiters instead of commas: | Representation | Syntax | |---|---| | Python list | [1, 2, 3, 4] | | NumPy array | [1 2 3 4] |

Random access to individual elements is still O(1) — the strides arithmetic computes a direct offset into the data buffer. The killer advantage, however, is vectorized operations. A single expression like a + b or np.dot(a. B) runs a compiled C loop over millions of elements without crossing back into Python.

Contiguous memory means all elements sit next to each other in RAM. The CPU's data-cache can load a whole chunk in one go, and the memory prefetcher can anticipate future accesses perfectly. Python lists spread elements across the heap, defeating both.

10.6.3 Worked Experiment — NumPy vs Python List Speed

For matrix multiplication or gradient computation, the gap is far larger:

• NumPy calls into highly tuned BLAS/LAPACK libraries (OpenBLAS, Intel MKL) that exploit SIMD vector instructions and cache tiling.
• Python nested loops would incur the pointer-chasing cost thousands of times per dot product.

10.6.4 NumPy in the ML Context

Every step of a typical ML pipeline touches NumPy arrays:

• Data ingestion: CSV/JSON is parsed into a NumPy array of features and labels.
• Preprocessing: X = (X - mean) / std vectorized over columns.
• Training loop: Gradients are NumPy arrays; matrix multiplications are np.dot.
• Model output: Predictions are NumPy arrays fed into plotting or evaluation.

Training data is almost always converted to NumPy arrays before being fed into models. Major ML frameworks — PyTorch (torch.from_numpy), TensorFlow (tf.convert_to_tensor), JAX (jnp.array) — all accept NumPy arrays directly as input.

10.6.5 Scope — When NumPy Wins, When It Does Not

10.6.6 Comparison — NumPy Array vs Python List

10.6.7 Pitfalls

Append is O(n). np.append(arr, val) does not grow the buffer in-place. It allocates a brand-new array of size n+1 and copies every existing element. Doing this in a loop turns an O(n) algorithm into O(n²). The correct pattern is pre-allocation:

# DO NOT DO THIS:
result = np.array([])
for x in data:
result = np.append(result, process(x))   # O(n²) — reallocation every iteration

# DO THIS:
result = np.zeros(len(data), dtype=np.float64)
for i, x in enumerate(data):
result[i] = process(x)   # O(n) — write into pre-allocated slot

View vs copy trap. Slicing a NumPy array returns a view. A new ndarray header that points into the same data buffer. Modifying the slice silently modifies the original:

a = np.array([1, 2, 3, 4])
b = a[:2]      # b is a view, not a copy
b[0] = 99
print(a)       # [99  2  3  4] — original changed!

Use .copy() (b = a[:2].copy()) when you need an independent array. The view mechanism is intentional. It avoids copying gigabytes of data when you only need a subarray — but it surprises new users.

dtype memory surprises. NumPy defaults to float64 (8 bytes per element). A 1000×1000 array is 8 MB. If your data are integers in [0, 255], using dtype=np.uint8 brings it to 1 MB. An 8× memory saving with no loss of precision. SEML Ch3 recommends choosing the smallest dtype that fits your data:

Using float32 for gradients in deep learning halves GPU memory usage with negligible impact on convergence.

Sparse data. When the array is mostly zeros (e.g., one-hot encodings, bag-of-words), storing the full dense matrix wastes memory. SciPy provides sparse matrix formats (scipy.sparse.csr_matrix) that store only non-zero entries and support NumPy-compatible operations. SEML Ch3 covers this in detail.

10.6.8 Q&A — "Why Is NumPy Faster Than Python Lists?"

10.6.9 Recap and Bridge to Pandas

NumPy gives you:

• A homogeneous, contiguous ndarray with a fixed dtype.
• Compiled C loops and BLAS calls → 100—1000× speedup on numerical workloads.
• Vectorized operations: avoid explicit Python for loops over array elements.
• Views for zero-copy slicing, but watch the append penalty.
• Choose dtypes carefully to control memory footprint.

The next data structure, Pandas DataFrames and Series, builds directly on NumPy ndarrays. A Pandas Series wraps a NumPy array plus an index. A DataFrame is a dictionary of Series sharing a common index. If NumPy is the engine, Pandas is the dashboard. We turn there now.

10.7 Pandas DataFrame in ML Systems

Loading a CSV is the first line of nearly every ML project. And that single line is already a data structure choice. pd.read_csv() returns a DataFrame. From that moment, every downstream decision about how you slice, filter, group. Feed data into a model is shaped by what a DataFrame is and what it is not.

10.7.1 Intuition — The Excel Spreadsheet of Python

A DataFrame is best understood as an Excel spreadsheet inside Python. It has labeled rows (the index) and labeled columns (the column names). Each column is a single Series — a one-dimensional labeled array built on a NumPy ndarray. So a DataFrame is a two-dimensional arrangement of Series that all share the same row index.

The critical leap from NumPy: NumPy arrays are homogeneous — every element in an ndarray must have the same dtype. A DataFrame relaxes this. The "name" column can store strings, the "age" column stores integers. The "salary" column stores floats — all in one table. Under the hood, each column is its own tightly packed NumPy array with a uniform dtype. The DataFrame itself is a dictionary of column-name → Series.

10.7.2 Definition

A Pandas DataFrame is a two-dimensional, labeled, tabular data structure built on top of NumPy. It is the standard way to load and manipulate CSV files and structured datasets in Python ML.

A DataFrame can store mixed data types across columns (unlike NumPy arrays, which are homogeneous). You typically create one from a dictionary, a list, a NumPy array, or directly from a dataset:

import pandas as pd
df = pd.DataFrame(data=iris.data, columns=iris.feature_names)

The data parameter holds the rows. The columns parameter labels each column with its feature name.

Series — the building block. Each column in a DataFrame is a Pandas Series. A one-dimensional labeled array wrapping a NumPy ndarray plus an index. Access a single column:

df["sepal length (cm)"]  # returns a Series

The Series still carries the underlying NumPy ndarray for vectorized computation. Adds label awareness — you can index by label (series["row_label"]) or by integer position (series.iloc[0]).

DataFrame as a collection of Series. Internally, a DataFrame stores a dictionary-like mapping from column names to Series objects. All Series share a common row index. This structure means:

• Each column can have its own dtype — float64 for measurements, object for strings, int64 for class labels.
• Column-level operations (sum, mean, std) run vectorized on the underlying NumPy buffers of each column.
• Row-level operations traverse across columns — slower because they cross type boundaries.

Object-typed columns (used for mixed-type data like strings-plus-None) lose the speed advantages of NumPy. The underlying array stores Python object pointers, not raw bytes. Whenever possible, use concrete dtypes (float64, int64, category) instead of object.

10.7.3 Worked Example — Iris Dataset End-to-End with Big O Annotations

from sklearn.datasets import load_iris
iris = load_iris()
df = pd.DataFrame(data=iris.data, columns=iris.feature_names)

y = list(iris.target)  # 150 class labels: 0, 1, 2

print(X.shape)  # (150, 4)

feature_index = {name: idx for idx, name in enumerate(iris.feature_names)}
# {'sepal length (cm)': 0, 'sepal width (cm)': 1, 'petal length (cm)': 2, 'petal width (cm)': 3}

X = df[iris.feature_names].to_numpy()

10.7.4 Scope — When to Use DataFrame vs Raw NumPy vs SQL

The DataFrame sits at a specific layer in the ML stack. Knowing its boundaries avoids wasted effort.

SEML Ch3 recommends the PyArrow backend (pd.read_csv(.... Dtype_backend="pyarrow")) for more memory-efficient types — Arrow strings use less RAM than Python object strings. Nullable integers avoid the float64 spillover that happens when Pandas encounters missing integer values.

For datasets larger than memory, Dask provides a Pandas-like DataFrame API with lazy evaluation and out-of-core computation across multiple cores. Polars offers a faster, multi-threaded alternative with a different API but similar concepts. Both are worth knowing when pd.read_csv() runs out of RAM.

10.7.5 Pitfalls

iterrows() is slow — avoid it. Iterating row-by-row with df.iterrows() or df.itertuples() defeats Pandas entirely. Each call returns a Python Series or namedtuple — forcing Python object construction, type dispatch. Interpreter overhead on every single row. SEML Ch3 reports iterrows() is about 5× slower than vectorized column operations for the same computation:

# DO NOT DO THIS — O(n) Python loop with per-row Series construction:
for idx, row in df.iterrows():
result[idx] = row["a"] + row["b"]

# DO THIS — vectorized across the entire column at once:
result = df["a"] + df["b"]   # NumPy-level loop, no Python per row

df.apply(func, axis=1) is better than iterrows() but still adds Python function-call overhead per row. For numeric columns, always prefer the vectorized expression directly on the Series.

Appending to a DataFrame is O(n). Every call to df = df.append(new_row) (or pd.concat([df. New_row]) in a loop) allocates a new DataFrame and copies all existing data. Doing this in a loop turns your code O(n²):

# DO NOT DO THIS:
df = pd.DataFrame()
for batch in batches:
df = pd.concat([df, batch])   # O(n²) — copies entire df each iteration

# DO THIS:
chunks = []
for batch in batches:
chunks.append(batch)
df = pd.concat(chunks)   # O(n) — single allocation with all data

The correct pattern is to collect pieces in a Python list (O(1) append) and call pd.concat() once at the end.

Mixed-type column surprises (dtype=object). If one value in a column of integers is None. Pandas may cast the entire column to float64 (because int64 has no NaN representation) or to object. An object column stores Python object pointers, losing all vectorization speed. Always inspect df.dtypes after loading:

df.dtypes
# sepal length (cm)    float64    ← good, homogeneous numeric
# species               object    ← bad: Python strings, no vectorization
# id                     int64    ← good, homogeneous integer

Use the PyArrow backend (dtype_backend="pyarrow") or Pandas' nullable dtypes (Int64 with capital I. string, boolean) to handle missing values without dtype degradation.

Chained indexing and the SettingWithCopyWarning. df[df["a"] > 0]["b"] = 0 may or may not modify the original DataFrame. It depends on whether intermediate steps return views or copies. Pandas warns but does not refuse. The safe pattern is .loc:

# Risky — may not modify df:
df[df["a"] > 0]["b"] = 0

# Safe — guarantees in-place modification:
df.loc[df["a"] > 0, "b"] = 0

10.7.6 Comparison — DataFrame vs NumPy ndarray

The relationship is not either-or. Every DataFrame column is backed by a NumPy ndarray. When the cleaning and feature engineering are done, the last step is df.to_numpy() to feed the model. DataFrame manages the labels and types; NumPy handles the numbers and speed.

10.7.7 Q&A — "Which Is the Best Data Structure?"

10.7.8 Recap — All Five Structures Working Together

Pandas DataFrame gives you:

• A 2D labeled table built on NumPy ndarrays — each column is a Series wrapping a typed array.
• Heterogeneous columns: strings in one column, floats in another, integers in a third — all in the same table.
• Vectorized column operations (df["a"] + df["b"]) that run at NumPy speed under the hood.
• Rich I/O: pd.read_csv(), pd.read_excel(), pd.read_sql() as entry points into ML pipelines.
• Avoid iterrows() (5× slower), avoid appending in a loop (O(n²)), and watch for dtype=object surprises.

The real-world flow is direct. Raw data (CSV, Excel, SQL, JSON) enters as a DataFrame, gets cleaned and engineered with column-wise vectorized operations. Then exits via .to_numpy() as a dense numeric array ready for model.fit(). The DataFrame is the bridge between messy real-world data and fast numerical computation. It is not a replacement for NumPy — it is the launchpad that prepares data for NumPy.

In the next section, we step back from the code-level data structures and examine the architectural patterns. The software design patterns that govern how these structures compose into maintainable ML systems.

10.8 Object-Oriented Programming for ML Systems

OOP is not a new language feature you learn from scratch. It is a way of organizing code — a mental model. The languages you already use (Python, Java, C++) all support OOP. The agentic AI frameworks you will use (CrewAI, LangChain, OpenAI Swarm) are built entirely on these principles. Understanding classes, objects, inheritance. Polymorphism is the difference between using those frameworks as black boxes and customizing them for your own needs.

10.8.1 Why OOP Matters in ML

So far, the code you have written — classification, regression, preprocessing — has been primarily functional. You call functions, pass data, get results. Data flows through a pipeline of transformations. That works beautifully for predictive and generative ML. A function takes input, returns output, and has no memory of the previous call.

But when you enter Agentic AI — building systems with multiple interacting agents — the practice shifts. An agent is not just a function. An agent has state (its configuration, its prompt, its conversation history) and behavior (what it does when invoked). You need to bundle that state and behavior together into one reusable unit. You need a class.

Whether you use CrewAI, OpenAI's Swarm, LangChain, or any agent framework, the underlying implementation is object-oriented. Agents are classes. Different agent types — validators, reviewers, summarizers, translators — inherit from a base agent class. Runtime polymorphism lets a single loop invoke agent.execute() on every agent without knowing which specific type it is calling.

Here is a quick comparison to anchor the two approaches:

10.8.2 Class and Object

Here is a concrete example. Imagine you write a Person class:

Class: Person
Properties: name, aadhaar_number, gender
Methods: walk(), talk(), sleep()

That class is just a definition. It occupies no real memory for a specific person. Now you create an object:

Object (instance of Person):
name = "Shreyas"
aadhaar_number = "1234..."
gender = "male"
→ can call walk(), talk(), sleep()

The class is the idea of a person. The object is Shreyas, a real person with a name and an Aadhaar number. You can create a thousand Person objects. Each with its own name, its own Aadhaar number, its own gender — from the same single class definition.

Class: Dog
Properties: name, breed_type, domestic_type, gender
Methods: run(), breathe(), play(), eat()

name = "Muddhu"
breed_type = "Shih Tzu"
domestic_type = "yes"
gender = "male"
→ can call run(), breathe(), play(), eat()

Now map this to your own classroom. Every student in this session is an object of the class Student. The class defines what a student is (properties: registration number, name, semester) and what a student does (methods: write_exam(), submit_assignment()). Each individual student is an instance with their own specific registration number, name, and semester. Same blueprint, different values.

10.8.3 Inheritance

Think of biological inheritance: children inherit traits from their parents (eye color. Height) but also have unique traits of their own (a specific skill, a scar). The parent's traits come for free; the child's uniqueness is added on top.

Class: Person
Properties: name, aadhaar, gender
Methods: walk(), talk(), sleep()

Class: Student (inherits from Person)
Inherited properties: name, aadhaar, gender          ← free from Person
Extra properties: registration_number, semester       ← Student-only
Inherited methods: walk(), talk(), sleep()            ← free from Person
Extra methods: write_exam(), submit_assignment()      ← Student-only

Class: Teacher (inherits from Person)
Inherited properties: name, aadhaar, gender           ← free from Person
Extra properties: employee_id                         ← Teacher-only
Inherited methods: walk(), talk(), sleep()             ← free from Person
Extra methods: evaluate_assignment(), teach()          ← Teacher-only

class Student(Person):          # Student IS-A Person
def __init__(self, name, aadhaar, gender, registration_number, semester):
super().__init__(name, aadhaar, gender)   # call parent's constructor
self.registration_number = registration_number
self.semester = semester

def write_exam(self):       # Student-only method
...

Everyday analogy: a smartphone is a phone that also has a camera and internet. A basic flip phone makes calls — that is the base class. A smartphone inherits the ability to make calls (it IS-A phone) and adds a camera, apps, and a browser. You did not redesign calling from scratch; you extended it.

Person
/      \
Student    Teacher
\      /
TeachingAssistant

10.8.4 Types of Inheritance

Picture these as arrows. Single inheritance is one arrow from parent to child (Person → Student). Multi-level is a chain (Vehicle → Car → Sedan). Hierarchical is a fan-out (Employee fans out to Manager, Developer, Designer). Multiple is a merge — two arrows converging on one child. Hybrid is a network combining all of the above.

The interface alternative. Many languages (Java, C#) restrict you to single inheritance to avoid the diamond problem. But they give you interfaces — contracts that define method signatures without implementations. A class can implement many interfaces. This gives you the flexibility of multiple inheritance (one class behaving as many types) without the ambiguity (no conflicting implementations). Python uses abstract base classes (ABCs) from the abc module to achieve the same pattern.

10.8.5 Polymorphism

Polymorphism and inheritance go hand in hand — inheritance provides the shared interface; polymorphism provides the different implementations. Without polymorphism, inheritance is just code reuse. Without inheritance, polymorphism has nothing to vary across.

There are two kinds, and the distinction between them is critical — both for understanding and for exams:

• Compile-time polymorphism (also called static polymorphism or function overloading). The decision about which method to call is made when the code is compiled. Based on the method signature (name + parameter list).
• Runtime polymorphism (also called dynamic polymorphism or method overriding). The decision about which implementation to execute is made while the program runs, based on the actual object type.

Think of it this way: compile-time polymorphism is about one name, many parameter lists. Runtime polymorphism is about one interface, many implementations.

10.8.6 Compile-Time Polymorphism — Function Overloading

Here is the step-by-step mechanism:

Class: Calculator
Method: add(a, b)       → returns a + b
Method: add(a, b, c)    → returns a + b + c

10.8.7 Runtime Polymorphism — Virtual Functions

Here is the step-by-step mechanism:

Class: Agent
Method: execute()   → declared, no implementation (virtual/abstract)

Class: ValidationAgent (inherits from Agent)
Method: execute()   → validates a paper: checks grammar, facts, structure

Class: ReviewAgent (inherits from Agent)
Method: execute()   → reviews content: gives feedback, assigns score

Class: SummaryAgent (inherits from Agent)
Method: execute()   → summarizes text: extracts key points, produces abstract

Class: TranslationAgent (inherits from Agent)
Method: execute()   → translates: converts text from one language to another

agents = [
ValidationAgent(),
ReviewAgent(),
SummaryAgent(),
TranslationAgent(),
FactCheckingAgent()      # added later — no changes needed anywhere else
]

for agent in agents:
agent.execute()

Why it is called "virtual function." In the parent class, the method is "virtual". It exists as a signature but not as a real implementation. The real code lives in the children. Each child writes its own logic under the same method name. In Python, all methods are virtual by default — any method can be overridden in a child class. In C++ and Java, you mark the method with the virtual keyword (C++) or allow overriding by default (Java). This enables the behavior.

Real-world parallel: scikit-learn's .fit() method. Every classifier in scikit-learn — LogisticRegression, RandomForestClassifier, SVC, KNeighborsClassifier — has a .fit(X, y) method. Same name, same parameter pattern, wildly different internal algorithms. You can write:

for model in [LogisticRegression(), RandomForestClassifier(), SVC()]:
model.fit(X_train, y_train)

The loop calls .fit() on each model without caring whether it is doing gradient descent. Building decision trees, or computing support vectors. That is runtime polymorphism in production ML code.

10.8.8 OOP in the Agentic AI Landscape

Agentic AI frameworks are not magical. Behind the YAML configs and the crew.kickoff() calls, you will find straightforward OOP:

• Classes define agent types: CrewAIAgent, LangChainAgent, SwarmAgent.
• Inheritance (usually single or multi-level) chains from a base Agent class. The base holds shared configuration — model name, temperature, prompt template. Children add role-specific logic.
• Runtime polymorphism gives every agent type a common method. run(), execute(), process(), invoke(). That the framework calls without knowing the specific agent type.
• Properties store configuration: self.model = "gpt-4", self.temperature = 0.7, self.prompt_template = "...". Each agent instance holds its own config.
• Methods implement behavior: validate(), summarize(), translate(), review(), generate(). Some are inherited from the base; others are overridden in children.
• Encapsulation hides internal complexity. You call agent.run(task) and do not see the HTTP calls, retry logic, or token counting happening inside.

When you customize a CrewAI agent — changing its role, its backstory. Its tools — you are setting properties on an object. When you define a new agent type that behaves differently from the built-in ones. You are creating a child class that inherits from the framework's base agent and overrides its execution method. When the framework orchestrates five agents in sequence, it is running a loop with runtime polymorphism. Calling .execute() on each agent in turn.

Bridge to 10.9: Now that you have the full toolbox — Big O, data structures. OOP — the next section puts them all together. You will see how a real ML pipeline assigns each data structure to a specific step in the workflow. Why each assignment is driven by the time complexity and mutability requirements of that step.

10.9 Putting It All Together — Data Structure Choices in a Typical ML Pipeline

You've seen lists, tuples, dicts, NumPy arrays, and DataFrames — each with its own complexity profile. Now the question is: who goes where in a real pipeline? The answer is never "whatever you feel like."

10.9.1 Symbol Registry

10.9.2 Standard Data Structure Assignments

A complete ML workflow uses every data structure for a specific reason. The table below pairs each pipeline step with its natural structure and the complexity contract that makes the pairing correct.

Each structure earns its place through its time complexity characteristics and its mutability contract. There is no "best" data structure — only the right one for the job.

10.9.3 The Pipeline Flow

CSV file ──▶ DataFrame ──▶ .values / .to_numpy() ──▶ NumPy array ──▶ model.fit()
│                                         │
│  column names → list                     │  shape → tuple
│  feature map → dict                      │  slicing → vectorized O(1) views
│
▼
Exploration, cleaning, and feature engineering
happen in DataFrame space because mixed types
and labeled axes make it ergonomic.

The transition from DataFrame to NumPy is the critical hand-off: data cleaning and exploration live in DataFrame space. Raw number crunching lives in NumPy. Every ML framework downstream — scikit-learn, TensorFlow. PyTorch — expects a NumPy array (or a tensor built on one) at fit() time.

10.9.4 One Key Pitfall

The most common mistake is reaching for the structure you know best instead of the one the problem demands.

• Using a list of lists for your feature matrix because "it's familiar". Then wondering why model.fit() is 10× slower than your classmate's.
• Using a dict for sequential feature names and losing column ordering.
• Using a mutable list for hyperparameters and accidentally mutating it between experiment runs.

Every structure has a complexity cost. The wrong choice does not break your code — it just makes it slow, fragile, or both.

10.9.5 Key Takeaway

The data structures you choose are the foundation. A model is only as fast as the arrays you feed it. Only as correct as the column mappings you build. Only as reproducible as the immutability contracts you respect. Pick each one deliberately, not by habit.

Exam Guidance Summary

Big O & Complexity

• Exam note: Understand Big O notation and the four main complexity classes: $O(1)$, $O(\log N)$, $O(N)$, $O(N\log N)$. You may be asked to rank them from fastest to slowest growth.

• Exam note: Be able to calculate ${\log }_2(N)$ by repeated division. For example, ${\log }_2(1024)=10$ because you can halve 1024 ten times before reaching 1. This directly maps to binary search step count.

• Exam note: Know the time complexity of list indexing ($O(1)$), dictionary key lookup ($O(1)$), and linear search ($O(N)$). Be prepared to identify which operation dominates in a given code snippet.

Data Structures

• Exam note: Know when to use each Python data structure (list vs tuple vs dictionary) in ML pipelines. The "why" matters as much as the "what" — mutability contracts (tuple is immutable. List is not) are a common exam differentiator.

• Exam note: Understand why NumPy is faster than Python lists. Homogeneous contiguous memory in C means the CPU can prefetch data and operate on entire blocks at once. Python lists store pointers to scattered objects; NumPy stores raw values packed together.

• Exam note: Know the Pandas DataFrame–NumPy relationship. A DataFrame is built on NumPy arrays internally. df.values or df.to_numpy() extracts the underlying array. This is the bridge from data wrangling to model training.

Object-Oriented Programming

• Exam note: Understand OOP fundamentals. Class (blueprint), object (instance), properties (data), methods (behavior), inheritance (reuse), polymorphism (one interface, many implementations).

• Exam note: Distinguish compile-time polymorphism (function overloading. Same name, different signatures, resolved at compile time) from runtime polymorphism (virtual functions / method overriding. Resolved at runtime via the object's actual type).

• Exam note: Understand why OOP matters for agentic AI frameworks. Agents are classes with shared state and behavior. Different agent types inherit from a base Agent class. Runtime polymorphism lets a single orchestration loop call agent.act() regardless of the concrete agent type. The core pattern behind CrewAI, Swarm, and LangChain.

Key Industry Applications

Inference & Retrieval

• Real-world: GPT-5.7 and similar LLMs — training time happens behind the scenes. Inference (read/search) time is what matters to users. This is why retrieval performance dominates ML system design. The billions of dollars spent on GPU clusters for training are invisible. The millisecond latency of a single token generation is what users feel.

Search & Traversal

• Real-world: Mobile phone contact search is a binary search ($O(\log N)$). Names stored alphabetically. Each step halves the search space. Even with 10,000 contacts, binary search finds the match in at most 14 comparisons. Fast enough that scrolling latency, not search, dominates the user experience.

• Real-world: Windows file system traversal uses trees with DFS/BFS algorithms. The same concepts appear in DOM traversal for web apps. When you call document.querySelector(), the browser walks the DOM tree — the same tree-walking pattern that os.walk() uses to traverse your filesystem. Different domains, identical data structure.

Numerical Computing

• Real-world: NumPy arrays underpin virtually all Python ML frameworks (TensorFlow, PyTorch, scikit-learn) through their fast C-level numerical operations. TensorFlow's tf.Tensor and PyTorch's torch.Tensor both wrap or interoperate with NumPy arrays. The .numpy() call on a PyTorch tensor is a direct bridge back to NumPy memory.

• Real-world: Pandas DataFrames are the standard for loading and preprocessing structured data (CSV, Excel, SQL) in ML pipelines. Before any model sees a single row. Data has passed through a DataFrame — cleaned, imputed, one-hot encoded. Normalized — using methods that internally dispatch to NumPy operations.

Agentic AI

• Real-world: Agentic AI frameworks (CrewAI, Swarm, LangChain) use OOP. Agents are classes. Different agent types inherit from a base class. Runtime polymorphism enables unified orchestration loops. A ResearcherAgent, CoderAgent, and ReviewerAgent all expose an execute(task) method. The orchestrator calls it without knowing which concrete agent it is dispatching to. This is the same pattern that makes plugin architectures, game entity systems, and GUI widget toolkits work.

The lecture concepts — complexity analysis, data structure selection, and OOP — are not abstract CS trivia. They are the operational reality of every production ML system, from the mobile search bar to the LLM serving infrastructure.