| 10^8 |
O(N) |
Linear search, single-loop iteration |
Linear: Time increases linearly with input size |
| 10^6 |
O(N log N) |
Merge sort, Quick sort, Heap sort |
Log-linear: Slightly worse than O(N), manageable for N=10^6 |
| 10^5 |
O(N√N) |
Prime sieve (optimized), computational geometry |
Linear root: More intensive than O(N), feasible for N around 10^5 |
| 10^4 |
O(N²) |
Bubble sort, Insertion sort, basic matrix ops |
Quadratic: Time grows as square of N, feasible for N≤10^4 |
| 10^3 |
O(N²√N) |
Nested loops with additional computation |
Higher-order: Grows faster than O(N²), suitable for small inputs only |
| 25 |
O(2ⁿ) |
Subset generation, backtracking algorithms |
Exponential: Doubles work exponentially with input size |
| 10 |
O(N!) |
Permutations, traveling salesman brute force |
Factorial: Extremely expensive, even N=10 results in 3,628,800 operations |