Given functions:
- $2^{\lg n} \lg n$
- $2^{1000}$
- $\lg \lg n$
- $n / 1000$
- $2^{2^{n}}$
- $\lfloor\sqrt{n}\rfloor$
- $n^{0.0001}$
- $\ln \left(\ln ^{2} n\right)$
- $4^{n}$
- $\lg ^{100} n$
- $n \lg n$
- $n \log _{4} n$
Is my ordering by growth rate correct (I am new to this)? Here $\lg n$ means $log_{2}$.
(a) $2^{1000}$ (It's a constant.)
(b) $\lg \lg n$ (Log of log grows extremely slowly.)
(c) $\ln \left(\ln ^{2} n\right)$ (Natural log of a square log.)
(d) $\lg ^{100} n$ (A power of log still grows slower than polynomial functions.)
(e) $\lfloor\sqrt{n}\rfloor$ (Root functions are sub-linear but grow faster than logarithmic functions.)
(f) $n / 1000$, $n \log _{4} n$ (Both are linear functions. The base-4 log is essentially a constant multiplier.)
(g) $n^{0.0001}$ (Tiny power, but it's still a polynomial.)
(h) $2^{\lg n} \lg n$, $n \lg n$ ($n$ times log $n$ grows faster than any polynomial but slower than exponentials.)
(i) $4^{n}$ (An exponential function.)
(j) $2^{2^{n}}$ (A double-exponential. It grows extremely fast.)
The functions in the same line (e.g., $n / 1000$ and $n \log _{4} n$) are in the same group, meaning their growth rates are equivalent and are represented by the $\Theta$ notation.