Good |
Fair |
Poor |
| Algorithm | Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|---|
| Average | Worst | Worst | ||||
| Depth First Search (DFS) | Graph of |V| vertices and |E| edges | - |
O(|E| + |V|) |
O(|V|) |
||
| Breadth First Search (BFS) | Graph of |V| vertices and |E| edges | - |
O(|E| + |V|) |
O(|V|) |
||
| Binary search | Sorted array of n elements |
O(log(n))
|
O(log(n))
|
O(1)
|
||
| Linear (Brute Force) | Array | O(n) |
O(n) |
O(1) |
||
| Shortest path by Dijkstra, using a Min-heap as priority queue |
Graph with |V| vertices and |E| edges | O((|V| + |E|) log |V|) |
O((|V| + |E|) log |V|) |
O(|V|) |
||
| Shortest path by Dijkstra, using an unsorted array as priority queue |
Graph with |V| vertices and |E| edges | O(|V|^2) |
O(|V|^2) |
O(|V|) |
||
| Shortest path by Bellman-Ford | Graph with |V| vertices and |E| edges | O(|V||E|) |
O(|V||E|) |
O(|V|) |
||
| Algorithm | Data Structure | Time Complexity | Worst Case Auxiliary Space Complexity | ||||
|---|---|---|---|---|---|---|---|
| Best | Average | Worst | Worst | ||||
| Quicksort | Array | O(n log(n)) |
O(n log(n)) |
O(n^2) |
O(log(n)) |
||
| Mergesort | Array | O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
O(n) |
||
| Heapsort | Array | O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
O(1) |
||
| Bubble Sort | Array | O(n) |
O(n^2) |
O(n^2) |
O(1) |
||
| Insertion Sort | Array | O(n) |
O(n^2) |
O(n^2) |
O(1) |
||
| Select Sort | Array | O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
||
| Bucket Sort | Array | O(n+k) |
O(n+k) |
O(n^2) |
O(nk) |
||
| Radix Sort | Array | O(nk) |
O(nk) |
O(nk) |
O(n+k) |
||
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Indexing | Search | Insertion | Deletion | Indexing | Search | Insertion | Deletion | ||
| Basic Array | O(1) |
O(n) |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
| Dynamic Array | O(1) |
O(n) |
O(n) |
- |
O(1) |
O(n) |
O(n) |
- |
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(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(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(n) |
| Red-Black 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(n) |
| Heaps | 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(log(n)) |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
|
| Binomial Heap | - |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
|
| Fibonacci Heap | - |
O(1) |
O(log(n))* |
O(1)* |
O(1) |
O(log(n))* |
O(1) |
|
| 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|) |
