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. &radic;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
| 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

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)
Only C is true.

Log bases do not matter.
by Veteran (50.9k points)

+1 vote