input size \( n \) |
\( n! \) |
\( 2^n \) |
\( n^3 \) |
\( n^2 \) |
\( n \log_2 n \) |
\( n \) |
\( \log_2 n \) |
\( 1 \) |
\( 10 \) |
\( \approx 3.6 \times 10^6 \) |
\( 1024 \) |
\( 1000 \) |
\( 100 \) |
\( \approx 33.2 \) |
\( 10 \) |
\( \approx 3.3 \) |
\( 1 \) |
\( 20 \) |
\( \approx 2.4 \times 10^{18} \) |
\( \approx 1.0 \times 10^6 \) |
\( 8000 \) |
\( 400 \) |
\( \approx 86.4 \) |
\( 20 \) |
\( \approx 4.3 \) |
\( 1 \) |
\( 500 \) |
\( \approx 1.2 \times 10^{1134} \) |
\( \approx 3.3 \times 10^{150} \) |
\( 1.25 \times 10^8 \) |
\( 250000 \) |
\( \approx 4482.9 \) |
\( 500 \) |
\( \approx 8.97 \) |
\( 1 \) |
\( 5000 \) |
\( \approx 4.2 \times 10^{16325} \) |
\( \approx 1.4 \times 10^{1505} \) |
\( 1.25 \times 10^{11} \) |
\( 2.5 \times 10^7 \) |
\( \approx 61438.6 \) |
\( 5000 \) |
\( \approx 12.3 \) |
\( 1 \) |
\( 1\,000\,000 \) |
\( \approx 8.2 \times 10^{5565708} \) |
\( \approx 9.9 \times 10^{301029} \) |
\( 10^{18} \) |
\( 10^{12} \) |
\( \approx 1.99 \times 10^7 \) |
\( 10^6 \) |
\( \approx 19.9 \) |
\( 1 \) |
\( 1\,000\,000\,000 \) |
\( \approx 9.9 \times 10^{8565705522} \) |
\( \approx 4.6 \times 10^{301029995} \) |
\( 10^{27} \) |
\( 10^{18} \) |
\( \approx 2.99 \times 10^{10} \) |
\( 10^9 \) |
\( \approx 29.9 \) |
\( 1 \) |
\( 10\,000\,000\,000 \) |
\( \approx 2.3 \times 10^{95657055186} \) |
\( \approx 4.4 \times 10^{3010299956} \) |
\( 10^{30} \) |
\( 10^{20} \) |
\( \approx 3.3 \times 10^{11} \) |
\( 10^{10} \) |
\( \approx 33.2 \) |
\( 1 \) |
## Rule of Thumb
For input size \( n \) and a time limit of 1 second, expect the time
complexity of the solution to be at least as good as \( f(n) \) such
that \( f(n) < 10^9 \). If \( f(n) \ge 10^9 \), then a solution with
time complexity of \( O(f(n)) \) is likely too bad to pass the tests
within 1 second.
## Example
With \( n = 1\,000\,000 \) and a time limit of 1 second, expect the
solution to have a time complexity of \( O(n \log n ) \). A solution
of time complexity of \( O(n^2) \) is likely too bad to complete the
tests within 1 second.