Big-O complexities of common algorithms used in By Eric http://bigocheatsheet.com/
Legend
Excellent |
Good |
Fair |
Bad |
Horrible |
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) |
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 | - |
O(1) |
O(1) |
O(1) |
- |
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 | - |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
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 | - |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
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) |
Array Sorting Algorithms
Algorithm | Time Complexity | Space Complexity | ||
---|---|---|---|---|
Best | Average | Worst | Worst | |
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) |
Timsort | O(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) |
Shell Sort | O(n) |
O((nlog(n))^2) |
O((nlog(n))^2) |
O(1) |
Bucket Sort | O(n+k) |
O(n+k) |
O(n^2) |
O(n) |
Radix Sort | O(nk) |
O(nk) |
O(nk) |
O(n+k) |
Graph Operations
Node / Edge Management | 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 Operations
Type | Time Complexity | |||||||
---|---|---|---|---|---|---|---|---|
Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge | ||
Linked List (sorted) | - |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(m+n) |
|
Linked List (unsorted) | - |
O(n) |
O(n) |
O(1) |
O(1) |
O(1) |
O(1) |
|
Binary Heap | O(n) |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
|
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) |
Big-O Complexity Chart
You must be logged in to post a comment.