Time Complexity Lookup

Data Structure & Alogirthm
16

Time complexity requirements for some algorithm competitions

n\le 10 \iff \mathcal{O}(n!)

n\le 15 \iff \mathcal{O}(3^n)

n\le 25 \iff \mathcal{O}(2^n)

n\le 50 \iff \mathcal{O}(n^5)

n\le 100 \iff \mathcal{O}(n^4)

n\le 500 \iff \mathcal{O}(n^3)

n\le 1000 \iff \mathcal{O}(n^2\log n)

n\le 5\times1e3 \iff \mathcal{O}(n^2)

n\le 2\times 1e5 \iff \mathcal{O}(n\sqrt{n})

n\le 1e6 \iff \mathcal{O}(n\log n), \mathcal{O}(n)

Some space considerations

int: 4 bytes

long long: 8 bytes

double: 8 bytes

long double: 16 bytes

Map and set will use a lot of memory (if enabled)

Generally, for 256MB, 64\times 1e6 int and 32\times 1e6 int can be enabled