question archive Solve the following question on asymptotic analysis
Solve the following question on asymptotic analysis
Subject:CommunicationsPrice:4.89 Bought3
Solve the following question on asymptotic analysis. (a) Prove that Ign = o(n") for any given constant c > 0 which is independent of n. (b) Prove and write down the pairwise relationships between the following functions in asymptotic notations: f(n) = 100n, g(n) = nitsin("), h(n) = nitsin(#), d(n) = n?. You may assume that domain of above functions are natural numbers. i.e N. (c) We define nt harmonic number as follows: H, =+ + + + ... + -. Show that i=n n (d) Prove or disprove the following statement for any pair of functions f, g : N - [1, co) f(n) = O(g(n)) implies Ig (f(n)) = O(lg (g(n))). Furthermore, prove or disprove it for little-o notation. (e) Using the above fact show that H,, = 0(lg n) (f) Prove that Ig(n!) = (nign). (g) Is the function [Ig n]! polynomially bounded? Is the function [Iglg n]! polynomially bounded?
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
(d)
False, f(n) = g(n) = n are a pair of such functions.
(e)
It's not hard to show that Hn = Θ(log n); in fact, we have the stronger inequalities ln(n + 1) ≤ Hn ≤ ln n + 1
(please see image E for the solution)
(f) please see image F below for the solution
(g)
(log?n)! is not polynomial bounded.
2. (loglogn)! is polynomial bounded.
Polynomial unbounded means for any k there exists a N such that when n>N , f(n)>nk
Polynomial bounded means there exists a N such that when n>N , f(n)<nk
f(n)<nk for some k
please see the attached file for the complete solution.
