Ordering algorithms from slowest to fastest

139 Views Asked by At

Given functions:

  1. $2^{\lg n} \lg n$
  2. $2^{1000}$
  3. $\lg \lg n$
  4. $n / 1000$
  5. $2^{2^{n}}$
  6. $\lfloor\sqrt{n}\rfloor$
  7. $n^{0.0001}$
  8. $\ln \left(\ln ^{2} n\right)$
  9. $4^{n}$
  10. $\lg ^{100} n$
  11. $n \lg n$
  12. $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.