Dark Mode

1,481 views

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!), & logn^{logn} 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 = logn^{logn}

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

Consider n = 2^{y}

then F1 = (log(2^{y}))! = y!

F2 = (2^{y})log(2^{y}) = y(2^{y})

F3 = (log(2^{y}))^{log(2^y)} = y^{y}

Clearly **y! is less than y ^{y}, it means F1 < F3.**

Now to compare F2 with F1 and F3, let us consider n = 2^{10}, then:

F1 = 10!,

F2 = 10 x (2^{10}) ∽ 10 x 1000 = 10^{4}

F3 = 10^{10},

and for n = 2^{100}

F1 = 100!

F2 = 100x(2^{100}) ∼ 100 x (1000^{10}) = 10^{(30 + 2)} = 10^{32}.

F3 = 100^{100} = 10^{200}

So it is clear that **F2 < F3**.

Now, How to compare F1 & F2 ?

for n = 2^{10},

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 2^{2} x (2^{2} + 1) x (2^{2} + 2) x (2^{2} + 3) x 2^{3} x (2^{3} + 1) x 10

The LEADING TERM of the above expression will be: 10 x 2^{(0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3)}= 10x2^{16}

F2 = 10 x 2^{10}

Similarly for n = 2^{100}.

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 >= 2^{5})

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

As n goes from 2^{10} to 2^{100} ,

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

F2 goes from 10x2^{10 }to 100x2^{100} so change in F2 = 10 x 2^{10} (10 x 2^{90 }- 1)

F3 goes from 10^{10 }to 10^{200} so change in F3 = 10^{10} (10^{190} - 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.