This table gives the maximum input size
This of course does not take into account any leading coefficients or more complicated expressions of the time complexity, but it gives a rough estimate.
For instance, if an
For every computation, the chosen base of the logarithm is
Complexity | Example | |||
---|---|---|---|---|
Interpolation search | ||||
Binary search | ||||
Divisors of |
||||
Array scan | ||||
Sieve of Erastothenes | ||||
Quick sort | ||||
Schönhage–Strassen's algorithm for multiplication | ||||
Shell sort | ||||
Divisors |
||||
Karatsuba's algorithm for multiplication | ||||
|
||||
Stooge sort | ||||
Strassen's algorithm for matrix multiplication |
||||
Naive matrix multiplication | ||||
Slowsort | ||||
Power set | ||||
TSP via dynamic programming |
||||
Naive TSP | ||||