Ordering by asymptotic growth rates
\[\begin{array}{cccccc} \lg(\lg^\ast n) & 2^{\lg^\ast n} & (\sqrt 2)^{\lg n} & n^2 & n! & (\lg n!) \\[2ex] \left(\frac 3 2\right)^n & n^3 & \lg^2 n & \lg(n!) & 2^{2^n} & n^{1/\lg n} \\[2ex] \ln \ln n & \lg^\ast n & n \cdot 2^n & n^{\lg \lg n} & \ln n & 1 \\[2ex] 2^{\lg n} & (\lg n)^{\lg n} & e^n & 4^{\lg n} & (n + 1)! & \sqrt {\lg n} \\[2ex] \lg^{\ast}(\lg n) & 2^{\sqrt {2 \lg n}} & n & 2^n & n \lg n & 2^{2^{n + 1}} \end{array}\]
- Rank the following functions by order of growth; that is, find an arrangement \(g_1\), \(g_2\), \(\cdots\) , \(g_{30}\) of the functions satisfying \(g_1 = \Omega(g_2)\), \(g_2 = \Omega(g_3)\), \(\cdots\) , \(g_{29} = \Omega(g_{30})\). Partition your list into equivalence classes such that functions \(f(n)\) and \(g(n)\) are in the same class if and only if \(f(n) = \Theta(g(n))\).
- Give an example of a single non-negative function \(f(n)\) such that for all functions \(g_i(n)\) in part (a), \(f(n)\) is neither \(O(g_i(n))\) nor \(\Omega(g_i(n))\).
A. Rank of The Functions
Let us first try to simplify as many functions as we can:
\[(\sqrt 2)^{\lg n} = 2^{\frac 1 2 \cdot \lg n} = n^{\frac 1 2} = \sqrt n \\[2ex] n^{1/\lg n} = n^{\lg 2/ \lg n} = n^{log_n 2} = 2 \\[2ex] n^{\lg \lg n} = (2^{\lg n})^{\lg \lg n} = (2^{\lg \lg n})^{\lg n} = (\lg n)^{\lg n} \\[2ex] 2^{\lg n} = n \\[2ex] 4^{\lg n} = 2^{2\lg n} = 2^{\lg n^2} = n^2 \\[2ex] lg^*(\lg n) = \lg^* n - 1\]The required order of the functions is as follows:
\[2^{2^{n + 1}} \\[2ex] 2^{2^n} \\[2ex] (n + 1)! \\[2ex] n! \\[2ex] e^n \\[2ex] n\cdot 2^n \\[2ex] 2^n \\[2ex] (3/2)^n \\[2ex] n^{\lg \lg n} = (\lg n)^{\lg n} \\[2ex] (\lg n)! \\[2ex] n^3 \\[2ex] n^2 = 4^{\lg n} \\[2ex] lg(n!) \approx n \lg n \\[2ex] 2^{\lg n} = n \\[2ex] (\sqrt 2)^{\lg n} = \sqrt n \\[2ex] 2^{\sqrt {2 \lg n}} \\[2ex] \lg^2 n \\[2ex] \ln n \\[2ex] \sqrt {\lg n} \\[2ex] \ln \ln n \\[2ex] 2^{\lg^\ast n} \\[2ex] \lg^* n \approx \lg^\ast(\lg n) \\[2ex] \lg(\lg^\ast n)) \\[2ex] n^{1/\lg n} = 1 \\[2ex]\]
B. Example Function
Such a function can be constructed by simply making it oscillate in a range which is bigger than the range of all the above mentioned functions. By doing so, the function will be larger than all of the above functions for some intervals and smaller in other intervals. And thus indeterminate whether asymptotically larger or smaller than the above functions.
Note that, \(2^{2^{n + 2}}\) is asymptotically larger and \(1/n\) is asymptotically smaller than all the above functions.
Now if we define our function as follows:
\[f(n) = \begin{cases} 2^{2^{n + 2}} & \text{if $n$ is even}, \\ \frac 1 n & \text{if $n$ is odd}. \end{cases}\]We have a function that can be asymptotically either larger or smaller than all functions \(g_i(n)\). Hence it is neither \(O(g_i(n))\) nor \(\Omega(g_i(n))\).