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.

~7 min read

1,396 words

7 Sections

Reviewed & Verified (2024 Syllabus)

Keys: [ Prev • ] Next

Array vs Linked List vs Hash TableTree & Graph OperationsSorting Bounds

In production systems and competitive programming, hardware limits enforce a strict runtime constraint: modern CPUs execute approximately $1 0^{8}$ basic operations per second. Knowing the asymptotic bounds of standard data structures and algorithms allows engineers to immediately evaluate whether an approach is physically viable before writing a single line of code.

Learning Objectives

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

Correlate input sizes ( $n \in [10, 1 0^{8}]$ ) with asymptotic bounds to identify viable algorithmic complexities under a 1-second CPU budget.
Compare the access, search, insertion, and deletion bounds of all major linear and hierarchical data structures.
Select sorting algorithms based on time/space trade-offs, in-place constraints, and stability requirements.
Identify graph algorithm runtimes, auxiliary space bounds, and precondition requirements (e.g., non-negative edge weights or acyclic constraints).

1. Asymptotic Growth Rates & 1-Second CPU Budgets

The following table benchmarks operational counts as $n$ scales, assuming a standard budget of $\approx 1 0^{8}$ operations per second:

Complexity	Name	$n = 10$	$n = 100$	$n = 1 0^{3}$	$n = 1 0^{6}$	Viable Input Size for 1 sec ( $1 0^{8}$ ops)
$O (1)$	Constant	$1$	$1$	$1$	$1$	Any input size ( $n \leq 1 0^{18}$ )
$O (lo g n)$	Logarithmic	$\approx 3$	$\approx 7$	$\approx 10$	$\approx 20$	Huge ( $n \leq 1 0^{18}$ )
$O (n <path d="M95,702$
c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14
c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54
c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10
s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429
c69,-144,104.5,-217.7,106.5,-221
l0 -0
c5.3,-9.3,12,-14,20,-14
H400000v40H845.2724
s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7
c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z
M834 80h400000v40h-400000z"/>)	Sublinear	$\approx 3$	$10$	$\approx 31$	$1 0^{3}$	Very Large ( $n \leq 1 0^{12}$ )
$O (n)$	Linear	$10$	$100$	$1, 000$	$1 0^{6}$	Large ( $n \leq 1 0^{8}$ )
$O (n lo g n)$	Linearithmic	$\approx 33$	$\approx 664$	$\approx 9, 965$	$\approx 2 \times 1 0^{7}$	Medium-Large ( $n \leq 1 0^{6}$ )
$O (n^{2})$	Quadratic	$100$	$10, 000$	$1 0^{6}$	$1 0^{12}$ (TLE)	Moderate ( $n \leq 5, 000$ )
$O (n^{3})$	Cubic	$1, 000$	$1 0^{6}$	$1 0^{9}$ (TLE)	$1 0^{18}$ (TLE)	Small ( $n \leq 400$ )
$O (2^{n})$	Exponential	$1, 024$	$1.26 \times 1 0^{30}$	Intractable	Intractable	Tiny ( $n \leq 22$ )
$O (n!)$	Factorial	$3.6 \times 1 0^{6}$	Intractable	Intractable	Intractable	Micro ( $n \leq 11$ )

2. Master Data Structure Operations Table

Values denote Worst-Case performance unless explicitly annotated as Amortized or Average.

Data Structure	Access by Index	Search by Value	Insert at Head	Insert at Tail	Insert Arbitrary	Delete at Head	Delete at Tail	Delete Arbitrary	Space Complexity
Static Array	$O (1)$	$O (n)$	—	—	—	—	—	—	$O (n)$
Dynamic Array	$O (1)$	$O (n)$	$O (n)$	$O (1)^{*}$	$O (n)$	$O (n)$	$O (1)$	$O (n)$	$O (n)$
Singly Linked List	$O (n)$	$O (n)$	$O (1)$	$O (1)^{†}$	$O (n)$	$O (1)$	$O (n)$	$O (n)$	$O (n)$
Doubly Linked List	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (1)$	$O (1)$	$O (1)^{‡}$	$O (n)$
Stack	—	$O (n)$	$O (1)$ [Push]	—	—	$O (1)$ [Pop]	—	—	$O (n)$
Queue	—	$O (n)$	—	$O (1)$ [Enqueue]	—	$O (1)$ [Dequeue]	—	—	$O (n)$
Deque	$O (1)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$	$O (n)$
Hash Table	—	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (1)^{avg} / O (n)$	$O (n)$
Binary Search Tree	—	$O (h) \to O (n)$	—	—	$O (h) \to O (n)$	—	—	$O (h) \to O (n)$	$O (n)$
AVL Tree (Balanced)	—	$O (lo g n)$	—	—	$O (lo g n)$	—	—	$O (lo g n)$	$O (n)$
Binary Heap	$O (1)$ [Peek]	$O (n)$	—	—	$O (lo g n)$ [Push]	$O (lo g n)$ [Extract]	—	$O (lo g n)$	$O (n)$

$^{*}$ Amortized $O (1)$ time for push-back; resizing takes $O (n)$ worst-case.
$^{†}$ Assuming a maintained tail pointer.
$^{‡}$ Given direct pointer reference to the target node.

3. Master Sorting Algorithms Table

Algorithm	Best Time	Average Time	Worst Time	Auxiliary Space	In-Place?	Stable?	Paradigm
Bubble Sort	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes	Yes	Comparison / Exchange
Selection Sort	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes	No	Comparison / Selection
Insertion Sort	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes	Yes	Comparison / Insertion
Merge Sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	No	Yes	Divide & Conquer
Quick Sort	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	Yes	No	Divide & Conquer / Partition
Heap Sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	Yes	No	Selection / Heap Structure
Counting Sort	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (k)$	No	Yes	Non-Comparison / Distribution
Radix Sort	$O (d \cdot (n + b))$	$O (d \cdot (n + b))$	$O (d \cdot (n + b))$	$O (n + b)$	No	Yes	Non-Comparison / Positional
Bucket Sort	$O (n + k)$	$O (n + k)$	$O (n^{2})$	$O (n + k)$	No	Yes	Non-Comparison / Bucketing

4. Master Graph Algorithms Table

Algorithm	Problem Solved	Time Complexity	Space Complexity	Graph Preconditions
BFS	Shortest path in unweighted graph	$O (V + E)$	$O (V)$	Any graph
DFS	Connectivity, cycles, flood-fill	$O (V + E)$	$O (V)$	Any graph
Kahn's (BFS)	Topological ordering	$O (V + E)$	$O (V)$	Directed Acyclic Graph (DAG)
Dijkstra	Single-Source Shortest Path (SSSP)	$O ((V + E) lo g V)$	$O (V)$	Non-negative edge weights ( $w \geq 0$ )
Bellman-Ford	SSSP & Negative Cycle Detection	$O (V \cdot E)$	$O (V)$	No negative cycles reachable from source
Floyd-Warshall	All-Pairs Shortest Path (APSP)	$O (V^{3})$	$O (V^{2})$	No negative cycles
Prim's	Minimum Spanning Tree (MST)	$O ((V + E) lo g V)$	$O (V)$	Connected, undirected graph
Kruskal's	Minimum Spanning Tree (MST)	$O (E lo g E)$	$O (V)$	Connected, undirected graph
Tarjan's	Strongly Connected Components	$O (V + E)$	$O (V)$	Directed graph

5. Key Takeaways

Input Bound Rule of Thumb: For $n \leq 1 0^{3}$ , $O (n^{2})$ algorithms pass comfortably; for $n \leq 1 0^{6}$ , $O (n lo g n)$ is required; for $n \geq 1 0^{8}$ , only strictly $O (n)$ or $O (lo g n)$ approaches complete within 1 second.
Cache Locality Trade-Off: While linked lists guarantee $O (1)$ head insertion, arrays frequently outperform them in wall-clock benchmarks due to cache lines and contiguous memory fetches.
Precondition Awareness: Always check edge-weight constraints before choosing between Dijkstra, Bellman-Ford, and Floyd-Warshall.

References & Academic Attribution

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapters 1–3, 6–9, 22–24. MIT Press.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.