Algorithm problem 6 [Problem3-3]
a. Rank the following functions by order of growth; that is,find an arrangement g1,g2,...,g30 of the functions satisfying g1 ∈ Ω(g2),g2 ∈ Ω(g3),...,g29 ∈ Ω(g30). Partition your list into equivalence classes such that ƒ(n) and g(n) are in the same class if and only if ƒ(n)∈Θ(g(n)).
- lg(lg∗ n) - 2^(lg∗ n) -( sqrt(2))^(lg n) - n^2 - n! - (lg n)! - (3/2)^n - n^3 - lg^(2)*n - lg(n!) - 2^2^n - n^(1/ lg n) - ln ln n - lg∗ n - n*2^n - n ^(lg lg n) - ln n - 1 - 2^(lg n) - (lg n)^(lg n) - e^n - n - 4^(lg n) - (n+ 1)! - (sqrt(lg n)) - lg ∗(lg n) - 2(sqrt(2 lg n)) - n - 2n - n lg n - 2^((2)^(n+1))
b. Give an example of a single nonnegative function ƒ(n) such that for all functions g(n) in part (a), ƒ(n) is neither in O(g(sub(i))(n)) nor in Ω(g(n)).