retagged by
529 views
4 votes
4 votes
Which of the following is/are TRUE?

1. n! = $\Theta$ ((n+1)!)

2.log n base 4 =$\Theta$ (log n base 2)

3. √log n = O (log log n)

A) 1 and 2 only

B) 1 and 3 only

C) 2 only

D) 1, 2 and 3 only
retagged by

2 Answers

3 votes
3 votes

Correct Option (C)  2 Only

Explanation:

(1) n!= Ɵ((n+1)!) implies that { (n! <= C1 . (n+1)! ) and  (n! >= C2 . (n+1)! ) }  

Where C1 and C2 are Some Constant. [By Definition of Ɵ- Notation ]

        since (n+1)! =(n+1) * n! 

         So (n! <= C1 . (n+1) * n! ) and  (n! >= C2 . (n+1) * n!  )

           ( 1  <= C1 . (n+1) ) and  (1 >= C1 . (n+1) )

            ( TRUE and FALSE )    = FALSE 

      So (1) Statement  is FALSE.

(2) log n base 4 =Θ (log n base 2)

    (log n base 4)    can be written as   ((log n base 2) * (log 4 base 2) ) 

                                                         =  ((log n base 2) * 2 )

                                                           So (2) statement is TRUE.

(3) Sqrt(log n)  = O (log log n) 

    =  Sqrt (log n) < = C .  (log log n)   

        = (1/2) . log (log n) <  =   C .{  log log log n }    [ By Taking log of both sides]

          = FALSE

  So (3) Statement is False.

0 votes
0 votes
Only C is true.

Log bases do not matter.
Answer:

Related questions

2 votes
2 votes
1 answer
2
0 votes
0 votes
0 answers
4
smsubham asked Apr 3, 2018
284 views
When T(n) = a T(n/b) + f(n)If on solving we get g(n) as upper bound solution for the recurrence.Is f(n) = O( g(n) ) always correct?