# Runtime Predictions

{% hint style="info" %}
These predictions are taken from this [Codeforces article.](https://codeforces.com/blog/entry/21344)
{% endhint %}

| n <=     | Allowed Time Complexity   |
| -------- | ------------------------- |
| 12       | $$O(n!)$$                 |
| 25       | $$O(2^n)$$                |
| 100      | $$O(n^4)$$                |
| 500      | $$O(n^3)$$                |
| $$10^4$$ | $$O(n^2)$$                |
| $$10^6$$ | $$O(n \log n)$$           |
| $$10^8$$ | $$O(n)$$                  |
| Others   | $$O(\log n)$$ or $$O(1)$$ |