Algorithms & Data Structures

Algorithms & Data Structures

At the core of every system that processes information is a set of decisions about how that information is stored and what operations are performed on it. Algorithms and data structures are not academic abstractions — they are the difference between a feature that runs in milliseconds and one that crashes under load.

Why Complexity Analysis Matters

Every algorithm has a cost. Big O notation describes how that cost scales. An O(n²) algorithm on a list of 1,000 items takes one million operations. Scale to one million items and you're at one trillion — a browser tab, not a web service. Understanding this shapes every architectural choice.

The key classes:

• O(1) — constant time: hash table lookup, array index access
• O(log n) — logarithmic: binary search, balanced BST operations
• O(n) — linear: single-pass array scan, linked list traversal
• O(n log n) — log-linear: merge sort, heap sort, efficient comparison-based sorting
• O(n²) — quadratic: naive nested loops, bubble sort on unsorted data

Foundational Data Structures

Arrays provide O(1) random access by index because elements are contiguous in memory. Insertion and deletion at arbitrary positions cost O(n) due to shifting. Dynamic arrays (like JavaScript arrays or Python lists) amortize the cost of resizing by doubling capacity, achieving O(1) amortized append.

Linked Lists trade random access for O(1) insertions and deletions at the head. Each node stores a value and a pointer to the next node. Doubly-linked lists add a back-pointer, enabling O(1) deletion anywhere if you already hold the node reference. They underpin queues, LRU caches, and adjacency lists.

Hash Tables achieve average O(1) insert, lookup, and delete by applying a hash function to keys, mapping them to array buckets. The challenge is collision handling. Separate chaining stores a linked list per bucket. Open addressing probes for the next available slot. A good hash function and load factor (ratio of entries to buckets, typically kept below 0.75) keep performance predictable.

Trees encode hierarchical relationships. A Binary Search Tree (BST) maintains the invariant that left children are smaller and right children are larger, enabling O(log n) search in balanced cases. Self-balancing trees (AVL, Red-Black) enforce balance through rotations, guaranteeing O(log n) worst case. Heaps are complete binary trees satisfying the heap property — max-heap: every parent ≥ its children — supporting O(1) max access and O(log n) insert/extract, making them ideal for priority queues.

Graphs are the most general structure: a set of vertices connected by edges, directed or undirected, weighted or unweighted. They model networks, dependencies, and state spaces. Represented as adjacency matrices (O(V²) space, O(1) edge lookup) or adjacency lists (O(V+E) space, efficient for sparse graphs).

Sorting Algorithms

Merge Sort divides the array in half recursively, sorts each half, then merges — O(n log n) guaranteed, stable, but requires O(n) auxiliary space.

Quick Sort picks a pivot, partitions around it, and recurses — O(n log n) average, O(1) extra space, but O(n²) worst case on already-sorted data (mitigated by randomized pivot selection).

Heap Sort builds a max-heap then repeatedly extracts the maximum — O(n log n) worst case, O(1) space, but poor cache performance due to non-sequential memory access.

For small arrays (n < ~20), Insertion Sort outperforms them all in practice due to low overhead and cache-friendly access.

Graph Traversal

Breadth-First Search (BFS) explores layer by layer using a queue, finding shortest paths in unweighted graphs. Depth-First Search (DFS) uses a stack (or recursion) to explore as deep as possible before backtracking — used for cycle detection, topological sorting, and connected components.

Dijkstra's algorithm extends BFS to weighted graphs, using a priority queue to always process the closest unvisited vertex — O((V + E) log V).

Applying This Knowledge

When building software, the question is not "which algorithm is fastest in theory" but "what are the access patterns?" A read-heavy system with few writes suits hash tables. Ordered range queries suit B-trees (used in every SQL database). Processing items in priority order suits heaps. Representing relationships suits graphs.

Profiling reveals where time is actually spent. Complexity analysis tells you whether optimization is linear — meaning faster hardware helps — or algorithmic, meaning a 1000x input size means 1,000,000x work.