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 f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).




b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n) is neither O(gi(n)) nor Ω(gi(n)).

Transcribed Image Text:

Igllg" n) 2n (V2)len n? n! (lg n)! n3 Ign lg(n!) 22" In In n Ig' n n's lgn n- 2" In n (lg n) 4's (n + 1)! Vlgn 2v2gn 21gm lg (lg n) 2" n lgn 22**1