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) | inf | inf
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.