Sorting Hat

A measure of how the running time of an algorithm grows as the input size n grows. It does not measure wall-clock time — it measures the number of operations. A nested loop over n items has time complexity O(n²) because you perform roughly n × n comparisons.

A measure of how much additional memory an algorithm uses relative to its input size. An algorithm that creates a copy of the input array uses O(n) extra space. One that works entirely with a fixed number of variables is O(1) — called constant or in-place.

The upper bound on an algorithm's growth rate in the worst case. When we say Merge Sort is O(n log n), we mean it will never perform more than roughly n × log₂(n) operations. Common classes from fastest to slowest: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ).

Ω(n) (Omega) is the lower bound — the best case. Θ(n) (Theta) means best and worst grow at the same rate, giving an exact characterisation. Insertion Sort on an already-sorted array runs in Ω(n); its worst case is O(n²); therefore Insertion Sort is not Θ in anything other than specific cases.

A sorting algorithm is stable if equal elements preserve their original relative order after sorting. This matters when you sort objects by one field and then by another — a stable second sort keeps the first sort's ordering intact within tied groups. Merge Sort and Insertion Sort are stable; Quick Sort and Heap Sort typically are not.

An algorithm sorts in-place when it rearranges elements within the original array using at most O(log n) extra memory (the call stack). Heap Sort is fully in-place. Merge Sort is not — it allocates temporary arrays proportional to the input size, giving O(n) space.

A problem-solving strategy that recursively splits a problem into smaller subproblems, solves each independently, then combines the results. Both Merge Sort (split → sort → merge) and Quick Sort (pivot → partition → recurse) follow this pattern. The recursion tree is why their complexity includes the log n factor.

Repeatedly walks through the array comparing adjacent pairs and swapping them if out of order. After each full pass, the largest unsorted element "bubbles" to its correct position at the end. Simple to understand but inefficient for large inputs — O(n²) average. Useful mainly as a teaching tool or for nearly-sorted tiny arrays.

Finds the minimum element in the unsorted region and swaps it to the front, then repeats for the remaining unsorted region. Always performs exactly O(n²) comparisons regardless of input order, but only O(n) swaps — making it useful when write operations are expensive (e.g., flash memory).

Builds the sorted array one element at a time by inserting each new element into its correct position among the already-sorted prefix. Behaves like sorting a hand of playing cards. Excellent for small arrays or nearly-sorted data — O(n) best case. Most standard libraries use it as the base case when input size drops below ~10-16 elements.

Recursively splits the array in half, sorts each half, then merges the two sorted halves into one. The merge step is the key: scanning two sorted lists simultaneously to produce one sorted list runs in O(n). Guaranteed O(n log n) in all cases and is stable, at the cost of O(n) auxiliary space.

Chooses a pivot element, partitions the array so all smaller elements are left of the pivot and all larger are right, then recurses on both sides. On average O(n log n) and in-place, making it the fastest general-purpose sort in practice. Worst case is O(n²) if the pivot repeatedly lands at an extreme — mitigated by randomising pivot selection.

Converts the array into a max-heap (a complete binary tree where each parent ≥ children), then repeatedly extracts the maximum and places it at the end. Guaranteed O(n log n) and in-place, but poor cache performance (accesses memory non-sequentially) makes it slower in practice than Quick Sort despite identical asymptotic complexity.

A binary heap is a complete binary tree stored as an array where the parent of index i is at ⌊(i-1)/2⌋ and children are at 2i+1 and 2i+2. Heapify is the operation that fixes heap order at a node by comparing with its children and swapping downwards. Building a heap from scratch using heapify bottom-up takes O(n), not O(n log n).

A graph is a set of vertices (also called nodes) connected by edges. A grid is a graph where each cell is a vertex and adjacency (up/down/left/right) defines the edges. Graphs can be directed (edges have direction) or undirected, and weighted (edges carry a cost) or unweighted.

Explores all neighbours of the current node before moving deeper. Implemented with a queue (FIFO). On an unweighted graph, BFS always finds the shortest path in terms of number of edges. It visits cells in expanding rings outward from the start, which is why the visited pattern looks like a growing circle.

Explores as far as possible down one branch before backtracking. Implemented with a stack (LIFO) — either an explicit stack or the call stack via recursion. DFS does not guarantee the shortest path; it may find a path that meanders far from optimal. Useful for maze generation, cycle detection, and topological sort.

Finds the shortest path in a weighted graph where all edge costs are non-negative. Maintains a priority queue sorted by current known distance from the source, always expanding the lowest-cost frontier node. On an unweighted grid, Dijkstra and BFS are equivalent. Named after computer scientist Edsger W. Dijkstra (1959).

An extension of Dijkstra that adds a heuristic — an estimate of how far the current node is from the goal. The priority queue sorts by g(n) + h(n), where g(n) is the actual cost from start and h(n) is the heuristic estimate to the goal. With an admissible heuristic (never overestimates), A* guarantees the optimal path while typically visiting far fewer nodes than Dijkstra.

A heuristic is a best-guess estimate used to guide search. For grid pathfinding, Manhattan distance — |Δrow| + |Δcol| — is the standard admissible heuristic when movement is restricted to 4 directions (no diagonals). It counts the minimum number of steps as if there were no walls. Euclidean distance is used when diagonal movement is allowed.

The frontier (also called the open set) contains nodes discovered but not yet fully explored. The visited or closed set contains nodes whose shortest path has been confirmed. Once a node moves from frontier to closed, it is never re-processed. This ensures each node is expanded at most once, keeping complexity manageable.

A maze generation algorithm that works by repeatedly dividing a rectangular chamber with a wall containing one passage, then recursively dividing each sub-chamber. The result is a "perfect maze" — there is exactly one path between any two cells. The direction of the dividing wall (horizontal or vertical) alternates or is chosen randomly each recursion.

A binary tree is a tree where each node has at most two children: left and right. A Binary Search Tree adds the ordering invariant: every value in a node's left subtree is less than the node's value, and every value in the right subtree is greater. This property enables O(log n) search on a balanced tree.

The root is the topmost node with no parent. A leaf is a node with no children. Every non-root node has exactly one parent; each node may have a left child, a right child, both, or neither. The root is the starting point for all traversals and operations.

The depth of a node is its distance from the root (root = depth 0). The height of a node is the length of the longest path from it down to a leaf. The height of the tree is the height of the root. A balanced BST with n nodes has height O(log n); a degenerate (linked-list shaped) BST has height O(n).

Visit the left subtree, then the current node, then the right subtree. On a BST, in-order traversal always yields elements in sorted ascending order — this is the unique property that defines the BST and makes it useful as a sorted container. The Glossary display at the bottom of this app shows the in-order sequence.

Pre-order: visit the node, then left, then right — useful for copying or serialising the tree structure. Post-order: visit left, then right, then the node — useful for deletion (you process children before parents) and evaluating expression trees. Neither produces a sorted sequence like in-order does.

Deleting a node with two children requires finding its in-order successor — the smallest node in its right subtree (the leftmost node of the right child). The successor's value replaces the deleted node's value, then the successor (which has at most one child) is removed from its original position. This preserves the BST property.

If you insert values in sorted order into a plain BST (e.g., 1, 2, 3, 4…), each node has only a right child — the tree degenerates into a linked list with O(n) height. Self-balancing variants like AVL Trees and Red-Black Trees automatically restructure (rotate) after insertions and deletions to keep height O(log n), guaranteeing fast operations regardless of insertion order.