Algorithms & Data Structures

What are Algorithms?

An algorithm is a finite, unambiguous sequence of instructions that solves a problem. The study of algorithms examines correctness (does it produce the right answer?) and efficiency (how much time and memory?). Data structures organise data so that algorithms can operate efficiently. Together they are the bedrock of computer science.

Big-O Complexity Classes

Time and Space Complexity

Big-O notation describes the asymptotic upper bound on running time as a function of input size n, ignoring constants and lower-order terms. Formally: f(n) = O(g(n)) if there exist c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

Practical significance: an O(n²) algorithm on n = 10&sup6 needs ~10¹² operations. An O(n log n) algorithm needs only ~2×10&sup7 — a 50,000× difference. Algorithm selection dominates hardware speed. No amount of hardware makes an O(n!) algorithm feasible for large n. Big-Omega (Ω) gives lower bounds; Big-Theta (Θ) gives tight bounds.

Sorting Algorithms

Python uses Timsort (hybrid merge + insertion sort). C++ STL uses Introsort (hybrid quicksort + heapsort + insertion). For almost-sorted data, insertion sort wins. Merge sort when stability is needed. Heap sort for guaranteed O(n log n) at O(1) space.

Binary Search and Divide & Conquer

Binary search finds an element in a sorted array in O(log n): compare with the middle; recurse on the relevant half. Just 20 comparisons suffice for 10&sup6 items.

Divide & Conquer : (1) divide into sub-problems; (2) solve recursively; (3) combine. Recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master Theorem. Examples: FFT O(n log n), Karatsuba multiplication O(n^1.585), Strassen matrix multiply O(n^2.81).

Graph Algorithms

Graphs G=(V,E) model relationships. Most real-world routing, scheduling, and network problems reduce to graph problems.

BFS — Breadth-First Search

O(V+E). Visits all neighbours first; uses a queue. Finds shortest path (unweighted graphs). Used in web crawlers, social network distance, flood fill.

DFS — Depth-First Search

O(V+E). Explores as deep as possible first; uses stack/recursion. Used in topological sort, cycle detection, SCCs, maze solving.

Dijkstra's Algorithm

O((V+E) log V) with priority queue. Shortest path from a single source in a non-negative weighted graph. Powers GPS navigation and OSPF routing.

Bellman-Ford

O(VE). Handles negative-weight edges and detects negative cycles. Used in BGP internet routing. Relaxes all edges V−1 times.

Floyd-Warshall (all-pairs shortest paths): O(V^3) for k in 1..V: for i in 1..V: for j in 1..V: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) Minimum Spanning Tree: Kruskal's: O(E log E) - sort edges, add if no cycle (union-find) Prim's: O((V+E) log V) - grow MST from a seed vertex

Dynamic Programming

Dynamic programming (DP) solves optimization problems by breaking them into overlapping sub-problems and storing solutions to avoid recomputation. Two approaches:

Memoisation (top-down): recursively solve, cache results (e.g., Fibonacci with memoisation: O(n) instead of O(2^n)).

Tabulation (bottom-up): fill a table from smallest sub-problems up; avoids stack overflow risk.

Classic DP problems: Fibonacci: F(n) = F(n-1) + F(n-2) O(n) time, O(n) space 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], v_i + dp[i-1][w-w_i]) O(nW) Longest Common dp[i][j] = dp[i-1][j-1]+1 (match) Subsequence: = max(dp[i-1][j], dp[i][j-1]) (no match) Edit Distance: dp[i][j] = min(insert, delete, replace) Coin Change: dp[i] = min dp[i-c] + 1 for each coin c

Greedy Algorithms

Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. They are simpler and faster than DP but correct only for specific problem structures.

Correct greedy: Kruskal's MST, Prim's MST, Dijkstra's (non-negative weights), Huffman coding (optimal prefix codes), interval scheduling (select by earliest finish time).

Incorrect greedy: 0/1 knapsack (fractional variant is greedy-solvable; integer is not), shortest path with negative edges, change-making with arbitrary coin systems.

NP-Completeness

The P vs NP question is the central unsolved problem in computer science. Definitions:

P: decision problems solvable in polynomial time.

NP: decision problems whose solutions are verifiable in polynomial time (but not necessarily solvable in polynomial time).

NP-complete: problems that are in NP and every NP problem can be reduced to them in polynomial time.

NP-hard: at least as hard as NP-complete problems; not necessarily in NP.

Famous NP-complete problems: Boolean Satisfiability (SAT), Travelling Salesman Problem (TSP), Graph Colouring, Hamiltonian Path, Subset Sum, Knapsack. If P = NP, all these problems have polynomial-time solutions — most cryptographic security would collapse. Most complexity theorists believe P ≠ NP, but the question remains open (Clay Millennium Problem, $1M prize).

Frequently Asked Questions

Both have O(n log n) average complexity, but quicksort has much better cache performance: it operates in-place, modifying the array with small, local memory accesses that stay in CPU cache. Merge sort requires O(n) extra space and frequently writes to separate memory locations (poor cache locality). Quicksort's constant factor in O(n log n) is roughly 2-3x smaller. However, quicksort's worst case is O(n²) with a bad pivot; randomised quicksort or median-of-three pivot selection makes worst-case extremely unlikely. Modern implementations like Introsort fall back to heapsort when recursion depth exceeds O(log n), guaranteeing O(n log n) worst case with quicksort's average performance.

Both break problems into sub-problems, but the key distinction is: divide and conquer breaks problems into independent, non-overlapping sub-problems (merge sort's two halves don't share elements). Dynamic programming handles overlapping sub-problems where the same sub-problem recurs many times (naive Fibonacci recomputes F(n-2) exponentially many times). DP avoids this by storing sub-problem solutions. Practical test: draw the recursion tree — if many nodes repeat, DP is applicable. Another DP requirement: optimal sub-structure (optimal solution contains optimal solutions to its sub-problems).

The two main strategies: (1) Separate chaining: each bucket points to a linked list (or tree for O(log n) worst case). Load factor can exceed 1; performance degrades gracefully. Python dicts, Java HashMap use variants of this. (2) Open addressing: on collision, probe another slot using linear probing (check i+1, i+2...), quadratic probing (i+1, i+4, i+9...), or double hashing. Requires load factor < 1; better cache performance due to contiguous memory. Robin Hood hashing variant reduces average probe length. A good hash function minimises collisions by distributing keys uniformly. SHA-256 and Murmur3 are commonly used. Cryptographic hash functions additionally guarantee one-wayness (for security applications).

A heap (binary min/max heap, or Fibonacci heap) supports O(1) find-min and O(log n) insert/delete-min. Ideal when you only need to repeatedly extract the minimum/maximum (priority queues, Dijkstra, heap sort, scheduling). A balanced BST (AVL, Red-Black, B-tree) supports O(log n) search, insert, delete, successor, predecessor, range queries, and in-order traversal. Choose BST when you need arbitrary lookup, ordered iteration, or rank queries. For implementing Dijkstra: binary heap is common; Fibonacci heap is O(V log V + E) theoretically better for dense graphs but complex to implement. In practice, binary heap edge over BST for pure priority-queue use cases due to better constants and cache behaviour.

Amortised analysis gives the average cost per operation over a sequence of n operations, even when individual operations vary in cost. Classic example: dynamic array (Python list) doubling. Each push_back is O(1) on average: most appends are O(1), but every doubling copies all elements — O(n). Total cost for n appends: n + n/2 + n/4 + ... = 2n = O(n). So each append is O(1) amortised. The three methods: aggregate (total cost / n), accounting (assign "credits" to cheap operations used during expensive ones), potential (define potential function representing stored work). Amortised O(1) push_back is why Python list.append() is efficient despite occasional O(n) resize.

TSP: given n cities and pairwise distances, find the shortest Hamiltonian cycle visiting each city exactly once. The naive solution checks all (n-1)!/2 routes — O(n!) — infeasible for n > 20. TSP is NP-hard; no polynomial-time algorithm is known, and most believe none exists. Practical methods: exact algorithms (branch-and-bound, dynamic programming Held-Karp: O(n²2^n) — feasible to ~n=25), approximation algorithms (Christofides' algorithm: 3/2-APX guarantee for metric TSP), heuristics (nearest neighbour, 2-opt local search, Lin-Kernighan). TSP appears in logistics, circuit board drilling, genome sequencing, and astronomy (telescope scheduling). In 2023, a revolutionary breakthrough in approximation for general metrics was achieved but exact polynomial-time remains elusive.

BFS (Breadth-First Search) explores level-by-level using a queue; DFS (Depth-First Search) explores as far as possible before backtracking, using a stack or recursion. BFS guarantees the shortest path in unweighted graphs — use it for: shortest-path problems, web crawling (level-by-level), social network shortest connection, finding connected components. DFS is better for: topological sorting, detecting cycles, finding strongly connected components (Tarjan's, Kosaraju's), solving mazes, generating permutations/combinations, tree traversals (pre/in/post-order). DFS uses O(depth) space; BFS uses O(width) space — for wide shallow graphs, DFS is more space-efficient; for narrow deep graphs, BFS wins.

Memoisation is the technique of caching the return value of a function keyed by its arguments, so repeated calls with the same arguments return immediately without recomputation. It applies when: (1) the function is pure (same inputs always give same output), (2) sub-problems overlap (the same inputs occur multiple times in a recursion tree). Classic example: Fibonacci. Without memoisation: O(2^n) time. With memoisation: O(n) time and O(n) space. Python's @functools.lru_cache decorator adds memoisation automatically. Memoisation is top-down DP; tabulation (building up a table from base cases) is bottom-up DP. Tabulation is often faster (no function call overhead) but requires knowing the order in which to fill the table.

A red-black tree is a self-balancing binary search tree with these invariants: (1) every node is red or black; (2) root is black; (3) no two consecutive red nodes; (4) all paths from a node to leaf have the same number of black nodes. These properties guarantee that the tree height is at most 2 log(n+1), ensuring O(log n) insert, delete, and search. It is the data structure behind C++ std::map, std::set, Java TreeMap, TreeSet, and Linux kernel's Completely Fair Scheduler. Compared to AVL trees: red-black trees have faster insertions/deletions (fewer rotations), while AVL trees are more strictly balanced (faster lookups). For workloads with more reads than writes, AVL is better; mixed workloads favour red-black.

P = NP would mean every problem whose solution can be quickly verified can also be quickly solved . Practical consequences of P = NP: RSA encryption would break (integer factorisation is in NP; if P=NP it is also in P), HTTPS, banking, SSH, and most cryptography would collapse. Drug discovery could be dramatically accelerated (protein folding and molecular design are NP-hard variants). Many planning, scheduling, and optimisation problems currently requiring approximations or heuristics would become exactly solvable in polynomial time. The overwhelming majority of theorists believe P ≠ NP, but a proof has eluded mathematicians for 50+ years. It is one of the Clay Mathematics Institute's Millennium Prize Problems with a $1 million reward.

Try it live

Everything above runs in your browser — open Hash Function Avalanche Visualizer and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.