in Algorithms edited by
1,481 views
2 votes
2 votes
F1 =(logn)! F2=(log(n!)) F3 = (logn)^logn

 

Just one query n! would be a constant rght , so in F1 we are taking factorial of a constant while in second one we are taking log of a constant so definitely F2 should be less than F1 .Am I correct or wrong at this point ?
in Algorithms edited by
1.5k views

3 Answers

0 votes
0 votes

f1=(logn)!=1*2*......logn=O(logn^logn)

f2= logn! = logn^n = O(nlogn)

f2= logn^logn=logn*logn*logn*...................logn times >n nut not nlogn
 

F1<F3<f2

 

0 votes
0 votes

In general, n is should be a variable unless it is explicitly mentioned that n is a constant.

If it is mentioned that n is a constant then n!, logn, (logn)!, log(n!), & lognlogn all of them would be constant for a given base of log.

Otherwise none of them would be.

Also if you are supposing n to be a constant then Logn is a smaller constant than n( unless the base of log is smaller than 1),

& n! is a constant bigger than n.

So in F1 we are taking factorial of a SMALLER CONSTANT & in F2 we are taking log of a BIGGER CONSTANT, so you can not argue like that.

It will depend on the difference between the two constants logn & n!.

------------------------------------------------------------------------------------------------

Answer to this question should be:

F2 < F1 < F3 for large values of n.

F1 = (logn)!

F2 = log(n!) = log(1 x 2 x 3 x … x (n – 1) x n) = log1 + log2 + log3 +…+ log(n – 1) + logn.

It can be observed that F2 can’t be more than nlogn.

let us consider F2 = nlogn, through out this analysis & at the end we will show that our final results would not be affected by this approximation.

F3 = lognlogn

Consider 2 is the base of logarithm, for F1, F2 & F3.(Any base >= 1 will work perfectly)

Consider n = 2y

then F1 = (log(2y))! = y!

F2 = (2y)log(2y) = y(2y)

F3 = (log(2y))log(2^y) = yy

Clearly y! is less than yy, it means F1 < F3.


Now to compare F2 with F1 and F3, let us consider n = 210, then:

F1 = 10!,

F2 = 10 x (210) ∽ 10 x 1000 = 104

F3 = 1010,

and for n = 2100

F1 = 100!

F2 = 100x(2100) ∼ 100 x (100010) = 10(30 + 2) = 1032.

F3 = 100100 = 10200

So it is clear that F2 < F3.


Now, How to compare F1 & F2 ?

for n = 210,

F1 = 10! = 1 x 2 x 3 x … x 10.

Writing 1 x 2 x 3 x … x 10 a little bit differently,

10! = 1 x 2 x (2 + 1) x 22 x (22 + 1) x (22 + 2) x (22 + 3) x 23 x (23 + 1) x 10

The LEADING TERM of the above expression will be: 10 x 2(0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3)= 10x216

F2 = 10 x 210

Similarly for n = 2100.

So clearly F2 < F1,

Now we have, F1 < F3, F2 < F3 & F2 < F1

So we can conclude that F2 < F1 < F3.

The only considerable approximation we have used in this analysis is F2 = log(n!) = nlogn

(although we also approximated 2^10 to 10^3 while comparing F2 & F3 but it is not going to affect the results since the difference between F2 & F3 is too big, even it is greater than F2 itself)

Even after giving F2 an extra edge over F1 & F3 by making it equal to its upper bound, it is still smaller than F1 & F3.

This means that our approximation for F2 has not affected our final results.

So the answer would be F2 < F1 < F3 for large values of n.( approximately for n >= 25)


Analysis of growth rates of F1, F2, & F3.

As n goes from 210 to 2100 ,

F1 goes from 10! to 100!, so change in F1 = 10!((100!/10!) - 1) 

F2 goes from 10x210 to 100x2100 so change in F2 = 10 x 210 (10 x 290  - 1)

F3 goes from 1010 to 10200 so change in F3 = 1010 (10190 - 1)

So roughly we can see here that growth rate is also F2 < F1 < F3, so growth rate of F1, F2 & F3 are also not going to affect our answer.

For more precise analysis of growth rate, after approximating n! using Stirling's Formula, derivatives of F1,  F2, & F3 can be used.

2 Comments

Ya understood but what about logn^log n ?
0
0
My earlier analysis was wrong  for large values of n & I also did not considered logn^logn.

I've updated the answer, you can check it now.

It should work for any n greater than or equal to 32.
0
0
0 votes
0 votes

F1 =(logn)! F2=(log(n!)) F3 = (logn)^logn

now F2 can be wriiten as n logn                              (n!=n^n)

let logn=x

F1=x!

F2=nx

F3=x^x

now F2<F1<F3

Related questions

1 vote
1 vote
3 answers
2