Time Complexity
Big-O Complexity Chart
Horrible | Bad | Fair | Good | Excellent |
Common Time Complexities
| Name | Time Complexity |
|---|---|
| Constant Time | O(1) |
| Logarithmic Time | O(log(n)) |
| Linear Time | O(n) |
| Quasilinear Time | O(nlog(n)) |
| Quadratic Time | O(n^2) |
| Exponential Time | O(2^n) |
| Factorial Time | O(n!) |
Common Data Structure Operations
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Array Sorting Algorithms
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
Searching Algorithms
| Algorithm | Time Complexity | Space Complexity | |
|---|---|---|---|
| Average | Worst | Worst | |
| Depth First Search (DFS) | N/A | O(|E| + |V|) | O(|V|) |
| Breadth First Search (BFS) | N/A | O(|V| + |E|) | O(|V|) |
| Binary Search | O(log(n)) | O(log(n)) | O(1) |
| Linear Search (Brute Force) | O(n) | O(n) | O(1) |
| Shortest path Dijkstra using a min-heap as priority queue | O((|V| + |E|) log|V|) | O((|V| + |E|) log|V|) | O(|V|) |
| Shortest path Dijkstra using an unsorted array as priority queue | O(|V|^2) | O(|V|^2) | O(|V|) |
| Shortest path by Bellman-Ford | O(|V||E|) | O(|V||E|) | O(|V|) |
Graphs
| Node/Edge Management | 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|) |
Heaps
| Heaps | Time Complexity | ||||||
|---|---|---|---|---|---|---|---|
| Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge | |
| Linked List (sorted) | N/A | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |
| Linked List (unsorted) | N/A | 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 | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| Fibinacci Heap | N/A | O(1) | O(log(n)) | O(1) | O(1) | O(log(n)) | O(1) |