Question

Algorithm problem

5 [3.2-3] Prove equation (3.19). Also prove that n!∈ω(2n) and n!∈o(n^n).

Answer 1

5)
n! = w(2n)
small omega definition://it is lowerbound which is not tight
f(n) is w(g(n)) if c*g(n)<f(n) where n0<n , n0,c are all values 0<c
now
f(n)=n!
g(n)=2n
now
c*g(n)<f(n)
c*2n<n!
let n=4
c*8<24
c<3
c=2
since we have c=2, n0=8 where cg(n)<f(n)
hence , n! is w(2n)

n! = o(n^n)
small-o definition//it is upperbound which is not tight
f(n) is w(g(n)) if f(n)<c*g(n)< where n0<n , n0,c are all values 0<c

f(n)=n!
g(n)=n^n
now
f(n)<cg(n)
n!<c*n^n
let n=1
1<c
c=2
n0=1
since we have such constants,
n! = o(n^n)