Part 00•Chapter 4 of 4•Foundational

Complexity & Big-O Quick Reference

Compact reference tables for time and space complexities of all major data structures and algorithms.

~14 min read

2,741 words

10 Sections

Academic Syllabus • CI Verified

Keys: [ Prev • ] Next

Array vs Linked List vs Hash TableTree & Graph OperationsSorting Bounds

In production engineering and competitive programming, physical hardware limits enforce a strict computational budget: modern enterprise CPUs execute approximately $1 0^{8}$ elementary operations per second on a single thread.

Knowing the exact asymptotic bounds, memory footprints, and architectural preconditions of standard data structures and algorithms allows software architects to determine whether an approach will succeed before writing a single line of code.

This chapter provides comprehensive, master reference tables for data structures, sorting algorithms, graph algorithms, and range-query engines, complete with 64-bit memory footprints and cache-efficiency metrics.

Learning Objectives

By the end of this chapter, you will be able to:

Correlate input scale constraints ( $n \in [10, 1 0^{18}]$ ) with viable algorithmic complexity classes under a 1-second CPU budget.
Evaluate the worst-case, average-case, and amortized time bounds for 16 primary data structures across index access, search, insertion, and deletion.
Select sorting algorithms based on theoretical stability, auxiliary memory overhead, and information-theoretic lower bounds ( $Ω (n lo g n)$ ).
Choose appropriate graph algorithms based on structural preconditions (cycles, negative edge weights, directed acyclic constraints).
Compare advanced range-query engines (Segment Trees, Fenwick Trees, Sparse Tables) across preprocessing, point update, and range query time profiles.

1. Hardware Physics & The 1-Second CPU Operations Budget

Wall-clock execution time is fundamentally bounded by the memory hierarchy and CPU instruction pipeline. While a 3.5 GHz CPU completes $3.5 \times 1 0^{9}$ raw clock cycles per second, instruction pipelining, branch mispredictions, and memory cache misses reduce effective throughput to approximately $1 0^{8}$ operations per second for algorithmic logic.

Memory Hierarchy Level	Hardware Latency (Cycles)	Latency Multiplier	Architectural Locality Impact
CPU Registers	~1 cycle	$1 \times$ (Baseline)	Immediate single-cycle instruction execution
L1 Data Cache	4 – 5 cycles	$4 \times$	~1.1–1.4 ns core cache hit (at 3.5 GHz; sub-nanosecond at >5.0 GHz)
L2 Cache	12 – 14 cycles	$14 \times$	Private per-core cache line access
L3 Shared Cache	40 – 60 cycles	$50 \times$	Cross-core unified cache interrogation
Main DRAM Memory	150 – 250 cycles	$200 \times$	Major pipeline bubble; execution pipeline completely stalled

Rough Competitive Programming Feasibility Heuristics

When presented with an input constraint $n$ under a standard 1.0-second runtime limit, use this table as an engineering and contest heuristic to narrow candidate algorithmic paradigms:

💡 Heuristic Principle:
These mappings are practical engineering rules of thumb, not immutable mathematical laws. Real-world feasibility depends directly on language overhead (e.g., C++ vs. Python), constant factor multipliers, CPU cache locality, SIMD branch predictability, and specific judge memory/time limits.

Input Scale Constraint $n$	Estimated Feasible Complexity	Archetypal Algorithmic Strategy	Canonical Examples
$n \leq 11$	$O (n!)$ or $O (n^{2} \cdot 2^{n})$	Factorial permutations, brute-force search	Traveling Salesperson (brute force)
$n \leq 22$	$O (2^{n})$ or $O (n \cdot 2^{n})$	Bitmask dynamic programming, backtracking	TSP via Held-Karp, Meet-in-the-Middle
$n \leq 100$	$O (n^{4})$	High-order polynomial dynamic programming	4-Sum brute check, 4D DP state transitions
$n \leq 400$	$O (n^{3})$	Cubic dynamic programming, all-pairs paths	Floyd-Warshall APSP, Matrix Chain Multiplication, Gaussian Elimination
$n \leq 5, 000$	$O (n^{2})$	Quadratic nested loops, pairwise comparisons	Insertion Sort, 2D Grid DP, Bellman-Ford
$n \leq 1 0^{5}$	$O (n n)$	Square root decomposition, block queries	Mo's Algorithm, Light/Heavy Decomposition
$n \leq 1 0^{6}$	$O (n lo g n)$ or $O (n lo g^{2} n)$	Divide-and-conquer, heap operations, sorting	MergeSort, QuickSort, Segment Trees, Dijkstra
$n \leq 1 0^{8}$	$O (n)$	Linear scan, two pointers, sliding window	Kadane's Algorithm, Prefix Sums, Kahn's BFS
$n \leq 1 0^{14}$	$O (n)$	Sublinear factorization, square root search	Trial division primality testing
$n \geq 1 0^{18}$	$O (lo g n)$ or $O (1)$	Logarithmic divide, binary search, math formulas	Binary search, GCD, modular exponentiation

2. Master Data Structures Operations Table

Conventions: $n$ = element count, $h$ = tree height ( $O (lo g n)$ balanced, $O (n)$ degenerate), $α = n / m$ = hash load factor. $^{*}$ denotes amortized time.

Data Structure	Access (Index)	Search (Value)	Insertion (Head)	Insertion (Tail)	Insertion (Arbitrary)	Deletion (Head)	Deletion (Tail)	Deletion (Arbitrary)	Auxiliary Space	64-Bit Memory Overhead Per Element
Static Array	$Θ (1)$	$O (n)$	—	—	—	—	—	—	$O (n)$	0 bytes (Raw contiguous primitive bytes)
Dynamic Array (Vector)	$Θ (1)$	$O (n)$	$O (n)$	$O (1)^{*}$	$O (n)$	$O (n)$	$O (1)$	$O (n)$	$O (n)$	$0 - 100%$ (Excess capacity buffer)
Singly Linked List	$O (n)$	$O (n)$	$O (1)$	$O (1)^{†}$	$O (n)$	$O (1)$	$O (n)$	$O (n)$	$O (n)$	8 bytes (`next` pointer + struct padding)
Doubly Linked List	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (1)$	$O (1)$	$O (1)^{‡}$	$O (n)$	16–20 bytes (`next` and `prev` pointers)
Stack (Array Backed)	—	$O (n)$	$O (1)^{*}$ [Push]	—	—	$O (1)$ [Pop]	—	—	$O (n)$	Contiguous buffer overhead
Queue (Circular Buffer)	—	$O (n)$	—	$O (1)$ [Enq]	—	$O (1)$ [Deq]	—	—	$O (n)$	Fixed circular array slots
Deque (Double Ended)	$Θ (1)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (n)$	Chunked array map pointers
Hash Table (Chaining)	—	$O (1)^{avg} / O (n)$	$O (1)$	—	$O (1)^{avg}$	$O (1)^{avg}$	—	$O (1)^{avg} / O (n)$	$O (n)$	Bucket array + linked list node pointers
Hash Table (Open Addr)	—	$O (1)^{avg} / O (n)$	—	—	$O (1)^{avg}$	—	—	$O (1)^{avg} / O (n)$	$O (n)$	Flat table array (Zero pointer overhead)
Binary Search Tree	—	$O (h)$	—	—	$O (h)$	—	—	$O (h)$	$O (n)$	16–24 bytes (`left`, `right`, `parent`)
AVL Tree (Self-Balancing)	—	$O (lo g n)$	—	—	$O (lo g n)$	—	—	$O (lo g n)$	$O (n)$	20–28 bytes (Pointers + height field)
Red-Black Tree	—	$O (lo g n)$	—	—	$O (lo g n)$	—	—	$O (lo g n)$	$O (n)$	17–24 bytes (Pointers + 1-bit color flag)
Binary Min/Max Heap	$O (1)$ [Peek]	$O (n)$	—	—	$O (lo g n)$ [Push]	$O (lo g n)$ [Pop]	—	$O (lo g n)$	$O (n)$	0 bytes (Implicit complete binary array)
Trie (Prefix Tree)	—	$O (L)$	—	—	$O (L)$ [Insert]	—	—	$O (L)$ [Delete]	$O (Σ \cdot N)$	$Σ \times 8 bytes$ per node ( $Σ = 26$ alphabet)
Disjoint Set Union (DSU)	—	$O (α (n))^{*}$	—	—	$O (α (n))^{*}$ [Union]	—	—	—	$O (n)$	Two flat integer arrays (`parent`, `rank`)

$^{†}$ Assuming a maintained tail reference pointer.
$^{‡}$ Assuming a direct pointer reference to the target node is provided.
$^{*}$ Amortized bound. $α (n)$ is the Inverse Ackermann function ( $α (n) \leq 4$ for all practical inputs $n \leq 1 0^{80}$ ).

3. Master Sorting Algorithms Benchmark Table

[!IMPORTANT] Information-Theoretic Lower Bound for Comparison Sorting: $Ω (n lo g n)$

Any comparison-based sorting algorithm can be modeled as a binary decision tree where each leaf corresponds to one of the $n!$ input permutations.

A binary tree of height $h$ has at most $2^{h}$ leaves: $2^{h} \geq n! ⟹ h \geq lo g_{2} (n!)$
By Stirling's Approximation ( $ln (n!) = n ln n - n + O (ln n)$ ): $lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + O (lo g n) = Ω (n lo g n)$
Therefore, no comparison sorting algorithm can beat $Ω (n lo g n)$ in the worst case.

Algorithm	Best Time	Average Time	Worst Time	Auxiliary Space	In-Place?	Stable?	Algorithmic Paradigm	Recommended Production Use Case
Bubble Sort	$Θ (n)$	$Θ (n^{2})$	$Θ (n^{2})$	$Θ (1)$	Yes	Yes	Comparison / Exchange	Academic pedagogy only
Selection Sort	$Θ (n^{2})$	$Θ (n^{2})$	$Θ (n^{2})$	$Θ (1)$	Yes	No	Comparison / Selection	Minimizing physical memory writes ( $O (n)$ swaps)
Insertion Sort	$Θ (n)$	$Θ (n^{2})$	$Θ (n^{2})$	$Θ (1)$	Yes	Yes	Comparison / Insertion	Small datasets ( $n \leq 32$ ) or nearly-sorted data
Merge Sort	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n)$	No	Yes	Divide & Conquer	External sorting, sorting linked lists ( $O (1)$ space)
Quick Sort	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n^{2})$	$Θ (lo g n)$	Yes	No	Divide & Conquer / Partition	General-purpose in-memory sorting
Heap Sort	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (1)$	Yes	No	Selection / Binary Heap	Systems with hard real-time latency and strict $O (1)$ space
Counting Sort	$Θ (n + k)$	$Θ (n + k)$	$Θ (n + k)$	$Θ (k)$	No	Yes	Non-Comparison / Distribution	Integers within a small bounded range ( $k \leq O (n)$ )
Radix Sort (LSD)	$Θ (d (n + b))$	$Θ (d (n + b))$	$Θ (d (n + b))$	$Θ (n + b)$	No	Yes	Non-Comparison / Positional	Fixed-width keys (e.g., 32-bit integers, IP addresses)
Bucket Sort	$Θ (n + k)$	$Θ (n + k)$	$Θ (n^{2})$	$Θ (n + k)$	No	Yes	Non-Comparison / Bucketing	Uniformly distributed floating-point numbers $[0.0, 1.0)$
TimSort	$Θ (n)$	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n)$	No	Yes	Adaptive Hybrid (Merge + Insert)	Default standard in Python (`sort()`) and Java (`Arrays.sort()`)
IntroSort	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (lo g n)$	Yes	No	Hybrid (Quick + Heap + Insert)	Default standard in C++ STL (`std::sort`)

4. Master Graph Algorithms Reference Table

Conventions: $V = ∣ V ∣$ (vertex count), $E = ∣ E ∣$ (edge count).

Algorithm	Problem Addressed	Time Complexity	Auxiliary Space	Graph Preconditions & Constraints
Breadth-First Search (BFS)	Shortest path in unweighted graphs	$Θ (V + E)$	$Θ (V)$	Any graph; finds minimal edge-count paths
Depth-First Search (DFS)	Reachability, cycle detection, bridges	$Θ (V + E)$	$Θ (V)$	Any graph; call stack bounded by $O (V)$
Kahn's Topological Sort	Topological linear ordering	$Θ (V + E)$	$Θ (V)$	Graph must be a DAG (zero directed cycles)
Dijkstra (Binary Heap)	Single-Source Shortest Paths (SSSP)	$Θ ((V + E) lo g V)$	$Θ (V)$	Edge weights must be non-negative ( $w (e) \geq 0$ )
Dijkstra (Fibonacci Heap)	Single-Source Shortest Paths (SSSP)	$Θ (E + V lo g V)$	$Θ (V)$	Non-negative edge weights; high constant factors
Bellman-Ford	SSSP & Negative Cycle Detection	$Θ (V \cdot E)$	$Θ (V)$	Detects negative weight cycles reachable from source
Floyd-Warshall	All-Pairs Shortest Paths (APSP)	$Θ (V^{3})$	$Θ (V^{2})$	Graph must contain zero negative weight cycles
Prim's Algorithm	Minimum Spanning Tree (MST)	$Θ ((V + E) lo g V)$	$Θ (V)$	Connected, undirected graph
Kruskal's Algorithm	Minimum Spanning Tree (MST)	$Θ (E lo g E)$	$Θ (V)$	Connected, undirected graph; utilizes DSU
Tarjan's SCC	Strongly Connected Components	$Θ (V + E)$	$Θ (V)$	Directed graph; single DFS pass using discovery & low-link values
Kosaraju's SCC	Strongly Connected Components	$Θ (V + E)$	$Θ (V)$	Directed graph; requires transposed reverse graph $G^{T}$
Edmonds-Karp	Maximum Network Flow	$O (V \cdot E^{2})$	$Θ (V + E)$	Directed graph with non-negative capacity constraints
Dinic's Algorithm	Maximum Network Flow	$O (V^{2} \cdot E)$	$Θ (V + E)$	Level graphs with blocking flows ( $O (E V)$ on unit networks)

5. Master Range Query Data Structures Table

When answering repeated range queries (Range Sum, Range Minimum/Maximum Query) over dynamic or static arrays of size $n$ :

Data Structure	Preprocessing Time	Range Query Time	Point Update Time	Range Update Time	Space Complexity	Supported Operations
Prefix Sum Array	$Θ (n)$	$Θ (1)$	$O (n)$	$O (n)$	$Θ (n)$	Static invertible operations (Sum, XOR)
Difference Array	$Θ (n)$	$O (n)$	$Θ (1)$	$Θ (1)$	$Θ (n)$	Batch range additions with offline queries
Sparse Table	$Θ (n lo g n)$	$Θ (1)$	$O (n)$	$O (n)$	$Θ (n lo g n)$	Static idempotent operations (RMQ: Min, Max, GCD)
Binary Indexed Tree (Fenwick)	$Θ (n)$	$Θ (lo g n)$	$Θ (lo g n)$	$O (n)$	$Θ (n)$	Dynamic prefix queries (Sum, Inversions)
Segment Tree (Standard)	$Θ (n)$	$Θ (lo g n)$	$Θ (lo g n)$	$O (n)$	$Θ (4n)$	Any associative operation (Sum, Min, Max, Matrix)
Segment Tree (Lazy Prop)	$Θ (n)$	$Θ (lo g n)$	$Θ (lo g n)$	$Θ (lo g n)$	$Θ (4n)$	Dynamic range updates + dynamic range queries
Square Root Decomposition	$Θ (n)$	$O (n)$	$Θ (1)$	$O (n)$	$Θ (n)$	Arbitrary dynamic queries, offline Mo's algorithm

6. Decision Flowchart: Selecting the Right Data Structure

System Architecture Mermaid

flowchart TD
    Root["What Operation Dominates Your Workload?"] --> KV["Fast Key-Value Lookup"]
    Root --> OT["Ordered Traversal & Extremum"]
    Root --> SEQ["Sequential LIFO / FIFO Access"]

    KV --> Q_KV{"Are keys ordered?"}
    Q_KV -- Yes --> RB["AVL / Red-Black Tree<br/><small>O(log n) search & ordered range</small>"]
    Q_KV -- No --> HT["Hash Table / Map<br/><small>O(1) average lookup & insert</small>"]

    OT --> Q_OT{"Is priority dynamic?"}
    Q_OT -- Yes --> HP["Binary Min/Max Heap<br/><small>O(1) peek, O(log n) push/pop</small>"]
    Q_OT -- No --> SA["Sorted Array + Binary Search<br/><small>O(log n) bisect, O(1) random read</small>"]

    SEQ --> Q_SEQ{"Is ordering strict?"}
    Q_SEQ -- LIFO --> STK["Stack (Array-Backed)<br/><small>O(1) push/pop, high locality</small>"]
    Q_SEQ -- FIFO --> QU["Queue / Deque (Ring Buffer)<br/><small>O(1) head pop, tail push</small>"]

7. Key Takeaways & Architectural Heuristics

The $1 0^{8}$ Operations Heuristic: On standard benchmark judges, targeting $f (n) \leq 1 0^{8}$ for the maximum given constraint $n$ serves as a dependable rule of thumb for sub-second execution (subject to cache locality and instruction complexity).
Memory Alignment Matters: Contiguous primitive arrays have zero pointer overhead and maximize L1/L2 cache prefetching; linked nodes incur 16–24 bytes of pointer overhead per element and cause cache stalls.
Comparison Sort Limit: No comparison-based sort can beat $Ω (n lo g n)$ in the worst case; beating this bound requires non-comparison distribution methods (Counting Sort, Radix Sort).
Idempotency in Range Queries: If the query function is idempotent ( $f (x, x) = x$ such as $min, max, g cd$ ), a Sparse Table answers queries in strict $O (1)$ time.

References & Academic Attribution

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215–225.