3-3 Ordering by asymptotic growth rates

a. Rank the following functions by order of growth; that is, find an arrangement \(g_1, g_2, \ldots , g_{30}\) of the functions \(g_1 = \Omega(g_2), g_2 = \Omega(g_3), \ldots, 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))\).

\[ \begin{array}{cccccc} \lg(\lg^{^\*}n) \quad & \quad 2^{\lg^\*n} \quad & \quad (\sqrt 2)^{\lg n} \quad & \quad n^2 \quad & \quad n! \quad & \quad (\lg n)! \\\\ (\frac{3}{2})^n \quad & \quad n^3 \quad & \quad \lg^2 n \quad & \quad \lg(n!) \quad & \quad 2^{2^n} \quad & \quad n^{1/\lg n} \\\\ \lg\lg n \quad & \quad \lg^\* n \quad & \quad n\cdot 2^n \quad & \quad n^{\lg\lg n} \quad & \quad \lg n \quad & \quad 1 \\\\ 2^{\lg n} \quad & \quad (\lg n)^{\lg n} \quad & \quad e^n \quad & \quad 4^{\lg n} \quad & \quad (n + 1)! \quad & \quad \sqrt{\lg n} \\\\ \lg^\*(\lg n) \quad & \quad 2^{\sqrt{2\lg n}} \quad & \quad n \quad & \quad 2^n \quad & \quad n\lg n \quad & \quad 2^{2^{n + 1}} \end{array} \]

b. Give an example of a single nonnegative 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))\).

b. For example,

for all functions \(g_i(n)\) in part (a), \(f(n)\) is neither \(O(g_i(n))\) nor \(\Omega(g_i(n))\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用