This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn’t be stumped when asked about them.
VisuAlgo.net. visualising data structures and algorithms through animation
Big-O Complexity Chart
Common Data Structure Operations
| Data Structure |
Time Complexity |
Space Complexity |
|
Average |
Worst |
Worst |
|
Access |
Search |
Insertion |
Deletion |
Access |
Search |
Insertion |
Deletion |
|
| Array |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Skip List |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| Hash Table |
N/A |
O(1) |
O(1) |
O(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Cartesian Tree |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Red-Black Tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Splay Tree |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL Tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| KD Tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
Array Sorting Algorithms
Graph Data Structure Operations
| Data Structure |
Time Complexity |
|
Storage |
Add Vertex |
Add Edge |
Remove Vertex |
Remove Edge |
Query |
| Adjacency list |
O(|V|+|E|) |
O(1) |
O(1) |
O(|V| + |E|) |
O(|E|) |
O(|V|) |
| Incidence list |
O(|V|+|E|) |
O(1) |
O(1) |
O(|E|) |
O(|E|) |
O(|E|) |
| Adjacency matrix |
O(|V|^2) |
O(|V|^2) |
O(1) |
O(|V|^2) |
O(1) |
O(1) |
| Incidence matrix |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|E|) |
Heap Data Structure Operations
| Data Structure |
Time Complexity |
|
Find Max |
Extract Max |
Increase Key |
Insert |
Delete |
Merge |
| Binary Heap |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
| Pairing Heap |
O(1) |
O(log(n)) |
O(log(n)) |
O(1) |
O(log(n)) |
O(1) |
| Binomial Heap |
O(1) |
O(log(n)) |
O(log(n)) |
O(1) |
O(log(n)) |
O(log(n)) |
| Fibonacci Heap |
O(1) |
O(log(n)) |
O(1) |
O(1) |
O(log(n)) |
O(1) |
Graph Algorithms
