The efficiency of an algorithm can be measured by two parameters:
Time Complexity
Time Complexity also known as running time of an algorithm is the number of primitive operations executed on a particular input.
Space Complexity
Space Complexity is the total (extra) memory space required by the program for its execution. The space complexity of an algorithm is the amount of memory space required to solve the computational problem.
Big-O Complexity chart [1]
Sorting Algorithms
| Algorithm | Time Complexity | Space Complexity | ||
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n2) | O(log(n)) |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | Ω(n) | Θ(n2) | O(n2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n2) | O(n2) | O(1) |
| Selection Sort | Ω(n2) | Θ(n2) | O(n2) | O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n2) | O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))2) | O(n(log(n))2) | O(1) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n2) | 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) |
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) |
| 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) |
| 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) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | 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) |
| 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) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Graph algorithms
| Algorithm | Time Complexity | Space Complexity | |
| Average | Worst | Worst | |
| DFS (Depth-first Search) | O(V + E) | O(V + E) | O(V) |
| BFS | O(V + E) | O(V + E) | O(V) |
| Djiskstra (shortest path) | O(V+E)*log(V) | O(V+E)*log(V) | O(V) |
| Bellman-ford (Shortest Path) | O(V*E) | O(V*E) | O(V) |
| Kruskal’s minimum spanning tree | O(E*logV) | O(E*logV) | O(|E|+|V|) |
| Prim’s minimum spanning tree (using adjacency Matrix) | O(V2) | O(V2) | O(1) |
Reference:
[1] Big-O Cheatsheet