[custurd122000]

I'm going to openly admit that this is homework but I cant find the answer in the book or on the web, but I worked it out and heres what I got I just need someone to check if its right

Is the function (log n)! polynomially bounded? In other words, does there exist a constanct c such that (log n)=0(n^c)?
Work:

(log n)! = 0(n^c)
nlogn <= n^c
lognlogn <= clog n
Let x=logn
x*x <= cx
cx is bigger therefore the function is polynomially bounded

[creative code monkey]

Not sure, but you may have more luck posting in a math forum somewhere....any math buffs out there?

[macosxnerd101]

Based on Ramanujan's approximation of log(n!), O(n log(n)) is appropriate. However, log(n!) != (log(n))!. The log(n!) dominates (log(n))!. Once you make that change, then yes, your math will be correct. And because log(n!) dominates (log(n))!, then (log(n))! is bounded by O(n^c).

I haven't had a lot of the formalities of CS in terms of algorithm analysis, so someone may clean up my answer some. But hopefully this helps some.

[Nikitin]

log(n!) is O(n log(n)) due to a basic fact that n! < n^n, no need for Ramanujan here.

log(n!) most definitely does not dominate (log(n))!, in fact it's the opposite.

To see why (logn)! is *not* polynomially bounded, you can assume that it is. So there is some constant 'k' such that (logn)! < n^c for sufficiently large n.

Whatever base b your log is in, just let n equal to b^x for some x.

Then your assumption states that x! < p^x for sufficiently large x (where p = b^c which is just a constant).

We already know that factorial cannot be bounded by an exponential like that. You should be able to solve this problem in itself.

So original assumption is wrong. And (logn)! is most definitely not bounded by any polynomial.