The Gateway to Computer Science Excellence
+4 votes
204 views
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
in Algorithms by Boss (16.4k points) | 204 views
0
what is 3) I couldnot understand
0
Sorry it is under root log n in LHS
+1
I think ans should be option C. 2 only,
Because for 3rd case put n=2^n .. you will get your ans .. and for 1st option you can think like n^2 != Theta ( n^3)
0
in 1) it is n! and (n+1)n!

we are not multiplying power

2 Answers

+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.

by Junior (529 points)
0 votes
Only C is true.

Log bases do not matter.
by Veteran (50.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,556 comments
105,368 users