- 10^7 I can make it in plenty of time.
- 10^8 Probably in time
- 10^9 Impossible except for very simple calculations
:
| 6.6 | 10! |
|---|---|
| 6.7 | 3 ** 14 |
| 6.9 | 2 ** 23, (n ** 3)(200), (nC(2n, n))(11) |
| 7 Can make it in plenty of time (n ** 2)(3000), (C(2n, n))(13) | |
| 7.1 | (n log n)(10 ** 6) |
| 7.4 | (n ** 3)(300) |
| 7.6 | 3 ** 16, 11! |
| 7.8 | 2 ** 26, (n ** 3)(400) |
| 7.9 | (n ** 2)(9000) |
| 8 Probably in time | |
| 8.1 | (n ** 3)(500), (nC(2n, n))(13) |
| 8.2 | (n log n)(10 ** 7), (C(2n, n))(15) |
| 9 much simpler, (n ** 3)(1000) |
Here, on the contrary, the usable algorithm is calculated backward from the constraints. - Typical ideas for coming up with solutions in competitive programming
This page is auto-translated from /nishio/計算量の見積もり using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.