edited by
446 views
1 votes
1 votes

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)$
  1. (i) & (iii) only
  2. (i) & (ii) only
  3. (ii) only
  4. (i),(ii) and (iii)
edited by

1 Answer

Best answer
3 votes
3 votes

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.

selected by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
465 views
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
343 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
456 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.