Question

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)).

Answer 1

Answer a

There are few things which needs to be remembered.

1. Exponential growth is much faster than polynomial functions. For example - 2ⁿ will grow faster than n²

2. Base of log does not matter as such. But base of exponential and degree of polynomial matters.

So based on that,

Please note that

• (lg n)^{lg n} => n^{lg lg n} as we know a^log_bc = c^log_ba
• lg*(lg n) = (lg*n)-1
• 4^{log n} = n^{log 4} = n²

Answer b

(lg ng (lg n)!n 2gn (2gn 2gn n lg (lg n) > 1 22 22n(n1)!> n!> e" > n.2" > 2" > )" > ng lg n (lg n)!> n n 49 n>n lg n n In n> Vig n 1/lg n 77 = 3 > 77 lg' (lg n) lg In ln n > >

f(n) = (1 + sin n).22