
Constraints are not tight so I use simple estimation:
when N <= 10, then both O(2^N) and O(N!) are ok when N <= 100, then O(N^3) is ok (I guess that N^4 is also ok, but never tried) when N <= 1.000, then N^2 is also ok when N <= 1.000.000, then O(N) is fine (I guess that 10.000.000 is fine too, but I never tried in contest) finally when N = 1.000.000.000 then O(N) is NOT ok, you have to find something better... 