Big-O time and space complexity for 27 common algorithms and data structures — sorting, searching, graph traversal, trees, and data structures. Filter by category and search by name.
This reference covers Big-O time and space complexity for 27 common algorithms and data structures, organized by category. Use it to compare sorting algorithms, understand graph traversal tradeoffs, and remember data structure operation costs during system design or technical interviews.
Big-O notation describes how the runtime or memory usage of an algorithm scales as the input size n grows. It expresses the upper bound of the growth rate — the worst-case scenario. O(1) means the algorithm takes constant time regardless of input size (e.g., hash table lookup, array access by index). O(log n) means runtime grows logarithmically — doubling n adds only one more step (e.g., binary search). O(n) is linear — each element is visited once. O(n log n) is typical of efficient sorting algorithms like Merge Sort and Timsort. O(n²) is quadratic — seen in simple nested-loop algorithms like Bubble Sort. O(2ⁿ) and O(n!) are exponential/factorial — practical only for very small n.
For sorting: prefer Timsort (Python default) or Quicksort with randomized pivot for general-purpose sorting; use Radix/Counting Sort for integers in a bounded range; use Merge Sort when stability is required and extra memory is available. For searching: Binary Search requires sorted data but is O(log n); use a hash table for O(1) average-case lookup with O(n) space. For graph problems: BFS for shortest path in unweighted graphs; Dijkstra for non-negative weighted graphs; Bellman-Ford when negative weights are possible. For key-value lookup: hash tables offer O(1) average; BSTs (AVL/Red-Black) offer O(log n) guaranteed with sorted iteration. For prefix/autocomplete: tries are O(m) per lookup where m is the key length.
A stable sort preserves the relative order of equal elements. For example, if you sort a list of {name, age} records by age, a stable sort guarantees that records with the same age appear in their original order. Stable sorts include Merge Sort, Timsort, Insertion Sort, Bubble Sort, Counting Sort, and Radix Sort. Unstable sorts include Quick Sort, Heap Sort, and Selection Sort. Stability matters when you sort by multiple keys sequentially (sort by last name, then by first name — requires stability on the second pass) or when the original order carries semantic meaning. Python's sorted() and list.sort() use Timsort, which is stable. JavaScript's Array.prototype.sort() is stable in V8 (Node.js, Chrome) and SpiderMonkey (Firefox) as of 2019.
Technical interviewers care about Big-O for two reasons: correctness (will this run in time?) and trade-off judgment (why this algorithm over another?). Always state your complexity before being asked. If you choose O(n²), explain why it's acceptable (small n, simpler code) or propose an O(n log n) alternative. System design implications: hash maps are the backbone of database indexes, caches, and routing tables — O(1) average lookup is why. Priority queues (heaps) power task schedulers, Dijkstra's algorithm, and A* search — O(log n) insert/extract-min is the key property. B-trees (not covered here, but related to BSTs) are used in databases and file systems for O(log n) range queries on disk with good cache locality.
Time complexity measures how the number of operations grows as input size n increases. Space complexity measures how much additional memory the algorithm requires as n grows. An algorithm can be O(n log n) time but O(1) space (Heap Sort) or O(n log n) time and O(n) space (Merge Sort). When memory is constrained (embedded systems, large datasets), prefer in-place algorithms with low space complexity even if they have similar time complexity.
Quick Sort's worst case occurs when the pivot is always the smallest or largest element — it degrades to O(n²) on already-sorted or reverse-sorted input with a naive pivot selection. The fix is randomized pivot selection (choose a random element) or median-of-three (pick the median of first, middle, and last). With randomized pivot, the worst case still exists but is astronomically unlikely. In practice, Quick Sort outperforms Merge Sort due to better cache locality — it sorts in-place with small constants, while Merge Sort requires O(n) extra memory. Most production sort implementations (Python's Timsort, Java's Arrays.sort) use a hybrid that picks the best algorithm based on input size and sortedness.
Use a hash map (O(1) average) when: you only need exact key lookups, you don't need sorted iteration, and the key space is hashable. Use a sorted set/map (BST, AVL, Red-Black, e.g., C++ std::map, Java TreeMap) when: you need range queries (find all keys between A and B), you need the minimum/maximum key, you need sorted iteration, or you need predecessor/successor queries. The sorted data structure costs O(log n) per operation vs O(1) average for a hash map, but provides ordering guarantees that hash maps cannot.
Amortized complexity describes the average cost per operation over a sequence of operations, even if individual operations occasionally cost more. The classic example is a dynamic array (Python list, C++ vector): most appends are O(1), but occasionally the array must be resized (doubled), which costs O(n). However, resizing happens so infrequently that the amortized cost per append is O(1). Similarly, hash table resizing is amortized O(1) per insertion. Amortized analysis explains why you should not fear the occasional expensive operation in a dynamic array — the cost is spread across many cheap operations.
Use your language's built-in sort. Python uses Timsort (stable, O(n log n) worst, O(n) best for nearly sorted data), Java uses Timsort for objects and a dual-pivot Quicksort for primitives, JavaScript V8 uses Timsort. Built-in sorts are highly optimized, tested, and have all edge cases handled. Implement your own sort only when: you have specialized knowledge about the data (integer range → radix sort), you need a specific stability guarantee the standard library doesn't provide, or you are building a systems component where the sort is a performance bottleneck and profiling confirms it.