Solution Found!
Ordering by asymptotic growth rates a. Rank the following
Chapter 3, Problem 3-3(choose chapter or problem)
Ordering by asymptotic growth rates
a. Rank the following functions by order of growth; that is, find an arrangement \(g_1,g_2,...,g_{30}\) of the functions satisfying \(g_1=\Omega (g_2),g_2=\Omega (g_3),...,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 \left(\lg ^{*} n\right) & 2^{\lg ^{*} n} & (\sqrt{2})^{\lg n} & n^{2} & n ! & (\lg n) ! \\
\left(\frac{3}{2}\right)^{n} & n^{3} & \lg ^{2} n & \lg (n !) & 2^{2^{n}} & n^{1 / \lg n} \\
\ln \ln n & \lg ^{*} n & n \cdot 2^{n} & n^{\lg \lg n} & \ln n & 1 \\
2^{\lg n} & (\lg n)^{\lg n} & e^{n} & 4^{\lg n} & (n+1) ! & \sqrt{\lg n} \\
\lg ^{*}(\lg n) & 2^{\sqrt{2 \lg n}} & n & 2^{n} & n \lg n & 2^{2^{n+1}}
\end{array}\)
b. Give an example of a single nonnegative function \(f(n)\) such that for all functions \(g(n)\) in part (a), \(f(n)\) is neither \(O(g(n)\) nor \(\Omega (g_\mathrm{i}(n))\).
Questions & Answers
QUESTION:
Ordering by asymptotic growth rates
a. Rank the following functions by order of growth; that is, find an arrangement \(g_1,g_2,...,g_{30}\) of the functions satisfying \(g_1=\Omega (g_2),g_2=\Omega (g_3),...,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 \left(\lg ^{*} n\right) & 2^{\lg ^{*} n} & (\sqrt{2})^{\lg n} & n^{2} & n ! & (\lg n) ! \\
\left(\frac{3}{2}\right)^{n} & n^{3} & \lg ^{2} n & \lg (n !) & 2^{2^{n}} & n^{1 / \lg n} \\
\ln \ln n & \lg ^{*} n & n \cdot 2^{n} & n^{\lg \lg n} & \ln n & 1 \\
2^{\lg n} & (\lg n)^{\lg n} & e^{n} & 4^{\lg n} & (n+1) ! & \sqrt{\lg n} \\
\lg ^{*}(\lg n) & 2^{\sqrt{2 \lg n}} & n & 2^{n} & n \lg n & 2^{2^{n+1}}
\end{array}\)
b. Give an example of a single nonnegative function \(f(n)\) such that for all functions \(g(n)\) in part (a), \(f(n)\) is neither \(O(g(n)\) nor \(\Omega (g_\mathrm{i}(n))\).
ANSWER:Step 1 of 4
Asymptotic notations are used to describe the running time of the algorithms. The worst, best and average running time of the algorithm is computed depending upon the size of the input. The given problem requires finding the decreasing order of the given complexities.