Algorithm Complexity Cheatsheet: The Ultimate Comparison
A comprehensive reference table for time and space complexities of sorting, graph algorithms, and common DSA patterns.
Memorizing complexities is one thing, but having a clear, comparative view of how different algorithms perform across best, average, and worst-case scenarios is essential for effective problem-solving and system design.
Sorting Algorithms
Algorithm
Best Case
Average Case
Worst Case
Space Complexity
Quicksort
O(N log N)
O(N log N)
O(N^2)
O(log N)
Mergesort
O(N log N)
O(N log N)
O(N log N)
O(N)
Heapsort
O(N log N)
O(N log N)
O(N log N)
O(1)
Bubble Sort
O(N)
O(N^2)
O(N^2)
O(1)
Insertion Sort
O(N)
O(N^2)
O(N^2)
O(1)
Selection Sort
O(N^2)
O(N^2)
O(N^2)
O(1)
Graph Algorithms
Algorithm
Time Complexity
Space Complexity
DFS / BFS
O(V + E)
O(V)
Dijkstra (with Binary Heap)
O((V + E) log V)
O(V)
Bellman-Ford
O(VE)
O(V)
Floyd-Warshall
O(V^3)
O(V^2)
Prim (with Binary Heap)
O((V + E) log V)
O(V)
Kruskal
O(E log E)
O(V)
Data Structure Operations
Structure
Access / Search
Insertion / Deletion
Hash Table
Avg O(1), Worst O(N)
Avg O(1), Worst O(N)
Balanced BST (AVL, R-B)
O(log N)
O(log N)
Stack / Queue
O(N) (top is O(1))
O(1)
Linked List
O(N)
O(1)
Want to see this in action?
Jump directly into the time complexity calculator to see how code translates to Big O growth.