Algorithm Time Complexity Cheat Sheet - Essential Big O Reference

This post is a quick, comprehensive Time Complexity Cheat Sheet summarizing the Worst-Case Time Complexity $O(\cdot)$ of the most important algorithms and data structure operations used in computer science. This is a vital resource for coding interviews, academic study, and software design.

Understanding Big $\text{O}$ notation is crucial for predicting an algorithm's performance and scalability as the input size $n$ grows.

1. Sorting Algorithms Time Complexity

Efficient sorting is a cornerstone of computer science. Here is the complexity analysis for standard comparison-based and non-comparison-based sorts.

Algorithm	Worst-Case Time Complexity (Time)	Space Complexity (Auxiliary)	Notes / Keyword Focus
Insertion Sort	$O(n^2)$	$O(1)$	Simple sort, good for small arrays.
Merge Sort	$O(n \log n)$	$O(n)$	Stable sort. Guaranteed $O(n \log n)$ performance.
Heapsort	$O(n \log n)$	$O(1)$	In-place sort using a Binary Heap.
Quicksort (Worst-Case)	$O(n^2)$	$O(n)$ or $O(\log n)$	High performance on average-case $O(n \log n)$ .
Counting Sort	$O(n+k)$	$O(n+k)$	Linear time. Requires input to be in range $[0, k]$ .
Radix Sort	$O(d(n+k))$	$O(n+k)$	Linear time. Sorts by digit (Non-Comparison Sort).

2. Data Structure Operations Complexity

The time cost of fundamental operations on core Data Structures.

Data Structure / Operation	Worst-Case Time Complexity	Keyword Focus / Notes
Binary Search (Sorted Array)	$O(\log n)$	Efficient searching method.
Hash Table (Insert/Delete/Search)	$O(1)$ (Average) / $O(n)$ (Worst)	Crucial for fast lookups. Worst case due to collisions.
Red-Black Tree (Insert/Delete/Search)	$O(\log n)$	Self-balancing BST, guarantees logarithmic complexity.
B-Tree (Insert/Delete/Search)	$O(\log_t n)$	Optimized for disk I/O (External Storage).
Heap (MAX-HEAPIFY)	$O(\log n)$	Used for Priority Queues and Heapsort.
Disjoint Sets (FIND-SET / UNION)	$\approx O(\alpha(n))$ (Amortized)	Inverse Ackermann function is nearly constant time.

3. Graph Algorithms Time Complexity

Complexity analysis for common Graph Algorithms, where $V$ is vertices and $E$ is edges.

Algorithm / Problem	Worst-Case Time Complexity	Keyword Focus / Notes
Breadth-First Search (BFS)	$O(V+E)$	Finds shortest paths in unweighted graphs.
Depth-First Search (DFS)	$O(V+E)$	Used for Topological Sort and finding cycles.
Prim's Algorithm (MST)	$O(E + V \log V)$ (Binary Heap)	Finds the Minimum Spanning Tree (MST).
Kruskal's Algorithm (MST)	$O(E \log E)$ or $O(E \log V)$	MST algorithm using the Disjoint Set structure.
Dijkstra's Algorithm (SSSP)	$O(E + V \log V)$	Single-Source Shortest Paths for non-negative weights.
Bellman-Ford Algorithm (SSSP)	$O(V E)$	Handles graphs with negative edge weights.
Floyd-Warshall Algorithm (APSP)	$O(V^3)$	Finds All-Pairs Shortest Paths using Dynamic Programming.

4. Dynamic Programming and Other Techniques

Algorithm / Problem	Worst-Case Time Complexity	Technique Used / Keyword
Matrix-Chain Multiplication	$O(n^3)$	Dynamic Programming optimization.
Longest Common Subsequence (LCS)	$O(mn)$	Dynamic Programming for sequence comparison.
Activity Selection	$O(n \log n)$	Greedy Approach (requires initial sort).
Fast Fourier Transform (FFT)	$O(n \log n)$	Divide-and-Conquer for signal processing/multiplication.

Summary of Common Big $\text{O}$ Classes

This table visually summarizes the hierarchy of performance for algorithm analysis.

Complexity Class	Name	Performance Rank	Example Algorithm
$O(1)$	Constant Time	Best	Accessing an array element by index.
$O(\log n)$	Logarithmic Time	Excellent	Binary Search.
$O(n)$	Linear Time	Good	Searching an unsorted array.
$O(n \log n)$	Linearithmic Time	Standard/Optimal	Merge Sort, Heapsort.
$O(n^2)$	Quadratic Time	Poor/Inefficient	Bubble Sort (Worst-Case).
$O(2^n)$	Exponential Time	Worst	Naive Traveling Salesperson Problem (TSP).

Conclusion

This Algorithm Complexity Cheat Sheet provides the foundational Big O values essential for any developer or computer science student. Mastering these complexities is the first step toward writing efficient, scalable code.

For full-stack developers, data scientists, and engineers, always prioritize algorithms with logarithmic or quasilinear ( $O(n \log n)$ ) complexity when possible!

Coding Streams

Algorithm Time Complexity Cheat Sheet - Essential Big O Reference

1. Sorting Algorithms Time Complexity

2. Data Structure Operations Complexity

3. Graph Algorithms Time Complexity

4. Dynamic Programming and Other Techniques

Summary of Common Big $\text{O}$ Classes

Conclusion

Related Posts

How Algorithms Evolve: From Naïve to Optimized

Was this article helpful?

1. Sorting Algorithms Time Complexity

2. Data Structure Operations Complexity

3. Graph Algorithms Time Complexity

4. Dynamic Programming and Other Techniques

Summary of Common Big O\text{O}O Classes

Conclusion

Related Posts

How Algorithms Evolve: From Naïve to Optimized

Get the Latest Updates

Was this article helpful?

Summary of Common Big $\text{O}$ Classes