Arrange the following functions in a list so that each function is the Big-O of the next function.

Question

Arrange in increasing order of complexity the list is: $\sqrt{n}, 1000\log(n), n \log(n), 2n!, 2^n, \frac{n^2}{1000}$

My answer is:

$$\sqrt{n}, 1000\log(n), n \log n, 2^n, 2n!,\frac{n^2}{1000}$$

Is this the right order in your opinion?

Thank you!

Answer 1

First, we know that a constant multiple of a function doesn't change the complexity of the functions, so our problem reduces to ordering the following functions:

$$\sqrt{n},\log(n), n \log(n), n!, 2^n, n^2.$$

It is helpful to remember a general hierarchy of functions, ordered by their growth complexity:

$$1 \to \log(n) \to n^c \to n^c\log(n) \to n^{c+\varepsilon}\to d^n \to n! \to n^n$$

where $c, \varepsilon \in (0,\infty)$ and $d \in (1,\infty)$.

When comparing two different powers of $n$, say $n^c$ and $n^d$ where $c,d\in (0,\infty)$, then we have: $$n^c \text{ is } \mathcal{O}(n^d) \iff c\leq d.$$

Similarly, for $c,d\in (1,\infty)$, $$c^n \text{ is } \mathcal{O}(d^n) \iff c\leq d.$$

This information is enough to uniquely order the functions as: $$1000\log(n), \sqrt{n},n\log(n),\frac{n^2}{1000}, 2^n, 2n!$$