I started to code some random problems from Project Euler. To have an extra hint of which kind of algorithm I’m looking for, I made the following table.
Read it like: “Assuming a computer can do 10 000 000 operations/sec, with a O(n^2) algorithm, you can solve a n ~ 3000 under a second”
| Complexity | n for 1 second | n for 1 minute |
|---|---|---|
| O(1) | infinite | infinite |
| O(lg(n)) | huge | 2^(10^7) |
| O(sqrt(n)) | 10^14 | 36*10^16 |
| O(n) | 10 000 000 | 600 000 000 |
| O(n*lg(n)) | 526 172 | 24 446 750 |
| O(n*sqrt(n)) | 46 415 | 711 378 |
| O(n^2) | 3162 | 24 494 |
| O(2^n) | 23 | 29 |
| O(n!) | 10 | 12 |
Project Euler problems should be solved under 1 minute (even in Python, most problems I solved has been < 2 secs), so if the input N is ~10 000 000, you should look for a O(n*lg(n)) solution or better.
Also if you’re developping Python code, you should have a look at these Python Time Complexity Tables. I think other language libraries use the same underlying datastructures and algorithms.