Test by Bikram | Algorithms | Test 2 | Question: 17

Question

Which of the following are TRUE?

1. $n! = \theta ((n + 1)!)$
2. $\log4 n   = \theta ( \log2 n  )$
3. $\sqrt{\log n} = O(\log \log n)$

• A. (i) & (iii) only
• B. (i) & (ii) only
• C. (ii) only
• D. (i),(ii) and (iii)

Comments

Can anyone explain the answer?

Answer 1

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)  log₄ n   = ϴ( log₂ n  ) is true as...
Let there exists some constant  C1 and C2 such that C1( log₂ n) <=  log₄ n and log₄ n <=  C2(log₂ n) for all n>=n0.

Let us find value of C1

C1<= (log₄ n / log₂ n )

C1<= (log₄ n . log_n 2)
C1<= log₄ 2
C1<= 1/2
 Similarly we can find value of C2

log₄ n <=  C2(log₂ n).
(log₄ n / log₂ n ) <= C2

(log₄ n . log_n 2)<= C2

log₄ 2<=C2
1/2 <= C2
Here we are able to find C1 and C2 which satisfy C1( log₂ n) <=  log₄ n and log₄ n <=  C2(log₂ n) for all n >= n0. Hence we can say that  log₄ n   = ϴ( log₂ n  ) is true
 

iii) √logn = O(log log n) is false as...
let n= 2^2^K

√logn= √(₂ K)= (₂ K/2)
log log n= K
We can't find a constant C such that 
(₂ K/2) <= CK for all n > =n0 where (log log n)= K

So right option is C.

Comments

can we not the value of c < 1/(n+1) . for it , condition would be satisfied . plzz explain why we cant take any value of c here.