CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Karim Pazoki
Karim Pazoki

Reputation: 969

Is O((log n)!) polynomial?

I wanna find O((log n)!). I think O((log n)!) and O(n!) are equal! Because I think when n is infinite (log n)! and n! are equal. Is it true? If yes how can I show that? If not is the O((log n)!) polynomial?

Upvotes: 4

Views: 13118

Answers (4)

kajacx
kajacx

Reputation: 12949

Since the proper math has already been done, let me add a more intuitive explanation of why O(log(n)!) > O(n^c) for any given c. We will assume the logarithm is base 2, and for simplicity choose c as 10. (The argument would work just as well with different numbers of general values).

So, why will log(n)! grow ever larger than n^10? Let's take a look at both functions' values at the powers of 2, more specificaly, how much greater they grew compared to the last power of 2. (n = 2^p from now on)

log(2^p)! = p * log(2^(p-1))!, (2^p)^10 = 2^10 * (2^(p-1))^10. This may seem complicated, but it tells us that the log(n)! function will multiply it's value at each pth power of 2 by p, but n^10 will multiply it's value only by 1024, so the log(n)! will grow ever larger eventually.

Also, log(n)! grows slower than any exponential, similar argument can be made by observing how much both function multiply their value when n grows by 1.

Upvotes: 2

user3118180
user3118180

Reputation:

I think your follow up question is whether (logn)! is polynomially bounded. It is obviously not a polynomial itself. Stirling’s Approximation gives us

n!≤en^[n+1/2]*e^(−n)

So,

(log n)!≤e(log n)^[1/2+log n]*e^(−log n)

Now (log n)^log n=(e^loglogn)^logn=e^[(logn)⋅(loglogn)]

So, the order of growth is approximately e^[(logn)(loglogn)−logn] =n^[(loglogn)−1]

This is unfortunately not bounded by any polynomial, since loglogn will eventually exceed any positive integer.

For example, compare (log n)! with n^2.

At n=e^10,(log n)!=3480, while (e^10)2≈4.85×108

At n=e^100,(log n)!≈10157 , while e^200≈1086

Upvotes: 7

karastojko
karastojko

Reputation: 1181

By using Stirling's approximation stating that $ n! ~ \sqrt{2 \pi n} \frac{n}{e}^n (1 + O(frac{1}{n})) $, and using the same formula for $ \log{n} $, one can check that for $ n! $ the leading factor is $ n ^ n $ while for $ \log{n}! $ the same factor becomes $ \log{n} ^ \log{n} $. By using the fact that $ \ln{n} \leq n - 1 $, I believe you can easily show that $ O(\log{n}!) $ is less than $ O(n!) $.

Upvotes: 0

pankaj
pankaj

Reputation: 1024

lets get back to some basic mathematics:
we know that if log a > log b, then a>b :(log base is greater than 1)
click here to get more on this

Now we know that log(N!)=NLogN (see here for proof)

and holding same argument,we get, log((log N)!)=logN logLogN
Since,
log(N!) is of polynomial degree ,and log((log N)!) is of logarithmic order,
clearly, O(N!) >O((logN)!)
hope this helps.

Upvotes: 0

Related Questions