i) n! = ϴ((n + 1)!) is false as...
we can't find any constant C1>0 such that C1((n+1)!) <= n! for all n>=n0
ii) log4 n = ϴ( log2 n ) is true as...
Let there exists some constant C1 and C2 such that C1( log2 n) <= log4 n and log4 n <= C2(log2 n) for all n>=n0.
Let us find value of C1
C1<= (log4 n / log2 n )
C1<= (log4 n . logn 2)
C1<= log4 2
C1<= 1/2
Similarly we can find value of C2
log4 n <= C2(log2 n).
(log4 n / log2 n ) <= C2
(log4 n . logn 2)<= C2
log4 2<=C2
1/2 <= C2
Here we are able to find C1 and C2 which satisfy C1( log2 n) <= log4 n and log4 n <= C2(log2 n) for all n >= n0. Hence we can say that log4 n = ϴ( log2 n ) is true
iii) √logn = O(log log n) is false as...
let n= 2^2^K
√logn= √(2 K)= (2 K/2)
log log n= K
We can't find a constant C such that
(2 K/2) <= CK for all n > =n0 where (log log n)= K
So right option is C.