| n | Max Time Complexity | Common Name |
|---|---|---|
| n <= 12 | O(n!) | Factorial |
| n <= 25 | O(2n) | Exponential |
| n <= 100 | O(n4) | Quartic |
| n <= 500 | O(n3) | Cubic |
| n <= 104 | O(n2) | Quadratic |
| n <= 106 | O(n log n) | Linearithmic |
| n <= 108 | O(n) | Linear |
| n > 108 | O(log n) or O(1) | Logarithmic and Constant respectively |
One trick to figuring out the expected time complexity is to substitute n and check that the result is 108.
Put another way: log10(n) should output 8.
For example:
log10(n!) is only equal to 8 when n is 12.
Similarly, log10(n2) is only equal to 8 when n is 104.
We consider 108 because that is usually the upper bound on the number of elements in most coding contests.
This technique is particularly helpful for more complicated complexity analysis. If you have O(MN log M) as the complexity of your algorithm, you can subsitute N and M (constraints) to determine if output is 10^8 and consequently whether your algorithm is fast enough.