Data Structures and Algorithms

An array (Python's list) stores elements in contiguous, indexed positions, which makes reading or writing element `i` fast regardless of the array's size — but finding whether a particular value exists anywhere in an unsorted array of n elements requires checking up to n of them one at a time. This cost is described using asymptotic notation: Big-O notation gives an upper bound on how an algorithm's running time grows as input size n grows, so a linear scan through an unsorted array of n elements is O(n) — its worst-case work grows in direct proportion to n. A hash table changes this picture entirely by mapping each key to an array position using a hash function, so that, per NIST's Dictionary of Algorithms and Data Structures, it is formally "a dictionary in which keys are mapped to array positions by hash functions," with performance that "may be constant (Θ(1)) if the table is big enough or grows". Worked example: looking up a user's profile by user ID in a list of 100,000 records means, worst case, scanning all 100,000; storing those same records in a hash table keyed by user ID turns that same lookup into essentially one computed array-index access.

That constant-time promise is not automatic — it depends on the hash function spreading keys evenly across array positions and on a collision-resolution scheme for the case where two different keys hash to the same position, which the NIST definition explicitly flags as the factor complexity "depends on". Common resolution strategies include chaining, where each array position holds a small list of all keys that hashed there, and open addressing, where a colliding key is placed in the next available slot according to a fixed probing rule. Choosing a data structure for a given task, then, is not a matter of memorizing which one is "best" in the abstract — it is a matter of matching the structure's guarantees (fast indexed access for arrays, fast average-case lookup for hash tables) to the operations the task actually performs most often.

Big-O's counterpart, Big-Omega notation, describes a lower bound on an algorithm's growth rate — the best case that still must be spent no matter how favorable the input. Together, these two notations let two algorithms solving the same problem be compared honestly: an algorithm that is O(n) in the worst case but Ω(1) in the best case (it can sometimes finish almost instantly) behaves very differently from one that is Θ(n) throughout, meaning its worst and best cases grow at the same rate. This vocabulary — O for upper bound, Ω for lower bound — is the shared language the rest of this module, and the wider field of algorithm analysis, uses to compare data structures and algorithms precisely rather than by anecdote.

A tree organizes data hierarchically through parent-child links rather than the flat, position-based layout of an array. A binary search tree (BST) is a particularly useful special case: NIST's Dictionary of Algorithms and Data Structures defines it as "a binary tree where every node's left subtree has keys less than the node's key, and every right subtree has keys greater than the node's key". Worked example: inserting the keys 50, 30, 70, 20, 40 in that order builds a tree with 50 at the root, 30 and 20/40 in its left subtree (all less than 50), and 70 in its right subtree (greater than 50); searching for 40 then means comparing against 50 (go left, since 40 30), then arriving at 40 — three comparisons instead of a linear scan through all five values, because at each step the ordering property eliminates roughly half the remaining candidates. This is exactly the structural property that MIT's introductory algorithms course (6.006) groups together with hash tables and heaps as the "elementary data structures" whose invariants make efficient operations possible in the first place.

Graphs generalize trees by dropping the restriction to a single parent per node. NIST DADS defines a graph formally as "a pair (V, E), where V is a set of vertices, and E is a set of edges between the vertices," with the simpler gloss that it is "a set of items connected by edges," each item called a vertex or node. An edge can be directed (a one-way relationship, such as "user A follows user B" in a social network) or undirected (a symmetric relationship, such as "city A is connected to city B by a road"). Graphs model relationships trees cannot: a city road network has cycles and multiple paths between the same two cities, which a tree's strict hierarchy forbids. Traversal algorithms — breadth-first search, which explores all of a vertex's immediate neighbors before moving further out, and depth-first search, which follows one path as far as possible before backtracking — are the basic tools for answering questions like "is there a route from A to B" or "what is the shortest number of hops between them," and both are core topics in MIT 6.006's coverage of graph searching.

Choosing between a tree and a graph representation, in practice, is a modeling decision driven by the relationships in the data: an organization chart, a file-system directory structure, and the binary search tree above are naturally hierarchical and map cleanly onto trees, while a road network, a social network, or a dependency graph among software modules generally cannot be forced into a tree without losing real relationships (a road that connects back to a city already visited would have to be dropped). Recognizing which shape the underlying relationships actually have is itself part of computational thinking: it determines which traversal and search algorithms are even applicable before any complexity analysis is done.

Binary search is the canonical example of an algorithm whose efficiency depends entirely on a precondition being met beforehand: Sedgewick and Wayne's algs4 reference implementation requires the input array to be sorted, and under that precondition it locates a target value, or determines it is absent, in O(log n) comparisons by repeatedly comparing the target to the middle element and discarding the half of the array that cannot contain it. Worked example: searching for 40 in the sorted array [10, 20, 30, 40, 50, 60, 70] starts by comparing 40 to the middle element, 40 — a match on the first comparison; searching instead for 45 would compare against 40 (45 is greater, so discard the left half and everything ≤ 40), then against 60 (45 is less, so discard the right half), narrowing to the single remaining candidate, 50, and reporting "not found" — three comparisons total on a seven-element array, versus up to seven for an unsorted linear scan. This is precisely why sorting an array first, even though sorting itself costs time, often pays for itself when many searches will follow.

Proving an algorithm correct — not just fast on the examples you happened to try — typically relies on identifying a loop invariant: a property that is true before the loop begins, remains true after every iteration, and, combined with the condition that ends the loop, implies the desired result. For binary search, the invariant is that if the target value is present in the array at all, it lies within the current low-to-high search window; each iteration either finds it or shrinks that window by discarding a half known not to contain it, and the loop terminates either by finding the target or by shrinking the window to nothing, at which point the invariant guarantees the target is genuinely absent. This kind of argument, central to the algorithm-analysis material MIT 6.006 builds its problem sets around, is what separates "I tested it on five inputs and it worked" from an actual guarantee that holds for every valid input, including ones never tried.

Sorting algorithms themselves span a wide range of correctness arguments and complexity trade-offs, from simple O(n²) approaches like insertion sort, which is easy to prove correct via an invariant that the front portion of the array is always sorted, to O(n log n) approaches like mergesort, whose correctness relies on the fact that merging two already-sorted halves can be done in a single linear pass. The choice between them in practice is rarely about which is asymptotically superior in isolation — O(n log n) always beats O(n²) for large enough n — but about the actual n involved, the memory available, and whether the data is already partially sorted, all of which are exactly the kind of considerations captured by comparing algorithms honestly through Big-O and Big-Omega bounds rather than by intuition alone.