Question

3-3 Ordering by asymptotic growth rates a. Rank the following functions by order of growth; that is, find an arrangement 81,82, 830 of the functions satisfying gi = Ω(82), g2 Ω(83), , g29 = Ω(g30). 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) = Θ(g(n)) Chaptr3 Growth of Functions 1n In Inn lg* g nn-2" n'ln Ig nIn n 2" nlgn 22+1 b. Give an example of a single nonnegative function f(n) such that for all func- tions gi (n) in part (a), f(n) is neither 0(gi(n)) nor Ω(gi (n))

Answer 1

Ordering by asymptotic growth rules: a) from the given above information the ranking is fairly straight forward and it has several identities like. n^lg lg n = (lg n)^lg n n^2 = 4^lg n n = 2^lg n 2 squareroot 2 lg n = n^squareroot 2/lg n 1 = n^1/lg n lg^* (lg n) = lg^* n - 1 for n > 1 For adding to this the V asymptotic bounds for sterling's formula r are helpful in ranking the expression factorials. n! = theta(n^n + 1/2 e^- n) lg(n!) = theta(n lg^n) (lg n)! = theta(lg n)^lg n + 1/2 e^-lg n)) for each term we have different equivalence class, where > symbol means W. 2^2n + 1 > 2^2n > (n + 1)! > n! > e^n > n.2^n > 2^n > (3/2)^n > n^lg lg n (lg n)^lg n > (lg n)! > n^3 > n^2 4^lg n > n lg n lg(n!) > A 2^lg n > (squareroot 2)^lg n > 2 squareroot 2 lg n > lg^2 n > ln n > squareroot lg n > In ln n > 2^lg * n