-
Notifications
You must be signed in to change notification settings - Fork 18
Time Analysis & Algorithms
Anupam Srivastava edited this page Aug 30, 2020
·
2 revisions
| Complexity | Max n | Examples |
|---|---|---|
| O(log n) | Very Large! | Binary search, Exponentiation by repeated squaring |
| O(n) | 100,000,000 | Linear search, Breadth-first search |
| O(n log n) | 5,000,000 | Merge-sort, Quick-sort, Heap-sort, Djikstra's algo |
| O(n^2) | 10,000 | Bubble-sort |
| O(n^3) | 400 | All-pairs shortest paths |
| O(2^n) | 25 | Listing all subsets |
| O(n!) | 11 | Listing all permutations |