> For the complete documentation index, see [llms.txt](https://interviews.woojiahao.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://interviews.woojiahao.com/other-technical-topics/runtime-predictions.md).

# 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)$$ |