Now as you have learned about the Time complexities of algorithms, their calculation and the Big-O notation. Before, we present you an exhaustive table of various known algorithms with their Big-O notation, we would show you approximate completion time for algorithms.
That if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2 seconds, where C is some constant that doesn’t change with the size of the input but depends on the platform.
That if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2 seconds, where C is some constant that doesn’t change with the size of the input but depends on the platform.
| Approximate completion time for algorithms, N = 100 | |
| O(Log(N)) | 10-7 seconds |
| O(N) | 10-6 seconds |
| O(N*Log(N)) | 10-5 seconds |
| O(N2) | 10-4 seconds |
| O(N6) | 3 minutes |
| O(2N) | 1014 years. |
| O(N!) | 10142 years. |
Array Sorting Algorithms
| Algorithm | Time Complexity | ||
|---|---|---|---|
| Best | Average | Worst | |
| Quicksort | O(n log(n)) | O(n log(n)) | O(n^2) |
| Mergesort | O(n log(n)) | O(n log(n)) | O(n log(n)) |
| Timsort | O(n) | O(n log(n)) | O(n log(n)) |
| Heapsort | O(n log(n)) | O(n log(n)) | O(n log(n)) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Shell Sort | O(n) | O((nlog(n))^2) | O((nlog(n))^2) |
| Bucket Sort | O(n+k) | O(n+k) | O(n^2) |
| Radix Sort | O(nk) | O(nk) | O(nk) |
Data Structure Operations
| Data Structure | Time Complexity | |||||||
|---|---|---|---|---|---|---|---|---|
| Average | 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) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Skip List | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) |
| Hash Table | - | O(1) | O(1) | O(1) | - | 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) |
| Cartesian Tree | - | O(log(n)) | O(log(n)) | O(log(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)) |
| 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)) |
| Splay Tree | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(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)) |
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) |