Algorithms

Big-O describes how long an algorithm takes as input size grows, ignoring constants. **O(1)** is constant time: indexing a list, getting a dict value. **O(log n)** is logarithmic: binary search, balanced-tree lookup. **O(n)** is linear: scanning a list once. **O(n log n)** is the sorting band: Python's TimSort, mergesort, heapsort. **O(n squared)** is quadratic and shows up in nested loops over the same data, like bubble sort or naive duplicate detection.

The mental model: double the input and ask how the time changes. Constant time stays flat. Linear time doubles. Quadratic time quadruples. Logarithmic time adds one step. This is what graders mean when they reject a working solution with "your code is correct but too slow". The complexity, not the language, is the bottleneck.

Memory complexity follows the same notation. A recursive function that holds n frames on the call stack uses O(n) extra space. An in-place sort uses O(1) auxiliary memory plus the call stack. Course rubrics at MIT 6.100L and Stanford CS106A award separate marks for time and space analysis.

Python's built-in **sorted()** returns a new sorted list. The method **list.sort()** sorts in place and returns None. Both use TimSort, a hybrid of mergesort and insertion sort with worst-case O(n log n) and best-case O(n) on partially sorted input. TimSort was invented for Python in 2002 and is now the default in Java and Android too.

The **key** parameter takes a function that returns the sort criterion for each element. `sorted(students, key=lambda s: s.gpa)` orders by GPA. Combine with `reverse=True` for descending order. For multi-level sorts, return a tuple from the key: `key=lambda s: (s.year, -s.gpa)` sorts by year ascending, then by GPA descending. TimSort is stable, which means equal keys keep their original order, so chained sorts compose correctly.

Writing your own sort is a learning exercise. In production code, the built-in beats hand-rolled bubble sort by 20x to 100x on lists of 10000 items because it is implemented in C. Implement bubble sort or insertion sort once to understand the mechanics, then use `sorted` for everything else.

Linear search scans the list one element at a time. Time complexity is O(n). It works on any iterable, sorted or not, and is the right choice for a list of 50 items or for one-off lookups.

Binary search needs a **sorted** list and runs in O(log n). It checks the middle element, discards half the list, and repeats. For 1 million items, linear search makes up to 1 million comparisons; binary search makes at most 20. The standard library module **bisect** implements this for you with `bisect_left` and `bisect_right`, which return the insertion index that would keep the list sorted.

Use bisect when the same sorted list is searched many times, such as a lookup table built once at startup. Use linear search when the list changes often, when sorting it first costs more than the savings, or when the data is small. Calling `bisect_left` returns the position where the target would go; combining it with an equality check tells you whether the target is present.

Recursion is a function that calls itself on a smaller version of the problem. Two parts are required: a **base case** that returns directly, and a **recursive case** that reduces the problem and calls the function again. Without a base case, the call stack grows forever and you get RecursionError on item 1000 (Python's default limit, raised with `sys.setrecursionlimit`).

Recursion shines when the problem has a tree structure: file-system traversal, parsing nested JSON, expression evaluation, divide-and-conquer algorithms. It struggles when the recursion is deep and linear, because each call adds a frame to the stack. A factorial of 10000 written recursively crashes. The same factorial written iteratively runs in milliseconds.

Tail-call optimization, which some languages use to make linear recursion stack-safe, is intentionally absent in Python. The Python position is that explicit loops are clearer than implicit recursion. Rule of thumb: if the recursive call is the last thing the function does and the recursion is linear, an iterative `for` loop is faster and uses constant stack space.

Dynamic programming solves a problem by combining solutions to overlapping subproblems and caching the results. The naive recursive Fibonacci has time complexity O(2^n) because `fib(5)` recomputes `fib(3)` three times and `fib(2)` five times. Caching shrinks it to O(n).

The decorator **@functools.lru_cache** does memoization for you. Apply it to a pure function (same input always returns the same output, no side effects) and Python stores recent results in an internal dictionary keyed by the argument tuple. The second call with the same arguments returns the cached value in O(1). The `maxsize` parameter caps cache memory; `maxsize=None` keeps everything, which fits coursework but not long-running services.

Memoization is one DP style; tabulation is the other. Tabulation fills an array bottom-up with explicit loops. Memoization is easier to write and reason about. Use tabulation when the recursion depth would exceed Python's stack limit or when you can drop the array down to constant space, which is the trick that turns Fibonacci into O(1) memory.

A graph is a set of nodes connected by edges. The simplest Python representation is a **dict adjacency list**: keys are nodes, values are the list of neighbors. `graph["A"] = ["B", "C"]` says A connects to B and C. This format scales to thousands of nodes and is what scikit-learn, NetworkX, and most coursework expect.

Breadth-first search (BFS) explores the graph level by level. It uses a **queue** (deque from collections, which gives O(1) popleft) and a **visited set** to avoid revisiting nodes. BFS finds the shortest path in an unweighted graph. Depth-first search (DFS) goes as deep as possible before backtracking. It uses a stack (a list with append and pop, or recursion) and the same visited set. DFS is the right tool for cycle detection, topological sort, and connected-components analysis.

Both run in O(V + E) where V is the number of nodes and E the number of edges. For a graph with 1000 nodes and 5000 edges, that is 6000 operations. The visited set is the critical detail: without it, cycles trap the traversal in an infinite loop.