[sam2k2002]

I have a problem for my homework where it asks me to:

Show that log(n!) = O(n log(n)). Do this by comparing n! with n^n.

I attempted to prove that n! is O(n), and I think I did that correctly, but I'm stuck here.

I generally don't understand Time Complexity. If you give me a couple loops, I can calculate the time complexity of the nested loops, etc. etc..

But on general principle questions like this one, I'm clueless... can someone help?

Thanks in advance,
Sam

[JosAH]

Have a look at Stirling's approximation for n!.

kind regards,

Jos

[Ganon11]

You can also use the fact that n! < n^n, and solve O(log(n^n)).

[JosAH]

Originally Posted by Ganon11

You can also use the fact that n! < n^n, and solve O(log(n^n)).

It's extremely tricky to use an upper bound, e.g. n < c*n^2 so O(n) == O(n^2)
which obviously isn't true.

kind regards,

Jos

[Ganon11]

Well, O(n) != O(n^2), but you can guarantee that n will never grow faster than n^2, so isn't n still O(n^2)? Or maybe I'm confused as to what Big-Oh notation means.

For instance, since you know n! grows slower than n^n, an upper limit for n^n is STILL faster than n!, so it can serve as an upper limit unless a more accurate upper limit can easily be found.

[Laharl]

Originally Posted by Ganon11

Well, O(n) != O(n^2), but you can guarantee that n will never grow faster than n^2, so isn't n still O(n^2)? Or maybe I'm confused as to what Big-Oh notation means.

For instance, since you know n! grows slower than n^n, an upper limit for n^n is STILL faster than n!, so it can serve as an upper limit unless a more accurate upper limit can easily be found.

All of this is correct. n < cn^2 for all n, so n is O(n^2).

In regards to the OP's question, if you show that n! < n^n, then you can take the log of both sides for log(n!) < nlog(n).

[r035198x]

None of you guys noticed that this is not really a Java question at all?

kind regards

r035198x(<--Non-mathematician surrounded by mathematicians)

[JosAH]

Originally Posted by Ganon11

Well, O(n) != O(n^2), but you can guarantee that n will never grow faster than n^2, so isn't n still O(n^2)? Or maybe I'm confused as to what Big-Oh notation means.

For instance, since you know n! grows slower than n^n, an upper limit for n^n is STILL faster than n!, so it can serve as an upper limit unless a more accurate upper limit can easily be found.

I think you mean it the other way around, i,.e. n! < n^n and you can skip the
'easily' part; if you can find a function f(n) such that n! <= f(n) < n^n then
n^n doesn't make it for a big-Oh for n! (see my silly little example).

kind regards,

Jos

[Laharl]

Jos, just because there's a more accurate upper bound doesn't mean that the other upper bound isn't accurate. f(n)=n is still O(n^2) (and O(n^3) and O(n^4) and...) because n < n^2. By analogy, since n! < n^n (there's probably some interval where this isn't true, we're starting at the upper end of that interval). Even if there is a function g(n) that is in between them, n^n is still an upper bound on n!. It just isn't the least upper bound (or tightest fit, for a more big-Oh phrase) anymore.

[JosAH]

Originally Posted by Laharl

Jos, just because there's a more accurate upper bound doesn't mean that the other upper bound isn't accurate. f(n)=n is still O(n^2) (and O(n^3) and O(n^4) and...) because n < n^2. By analogy, since n! < n^n (there's probably some interval where this isn't true, we're starting at the upper end of that interval). Even if there is a function g(n) that is in between them, n^n is still an upper bound on n!. It just isn't the least upper bound (or tightest fit, for a more big-Oh phrase) anymore.

Big-Oh wise speaking, we have to take the smallest function; otherwise the entire
thing would be moot:, e.g. searching through an unordered list can be done in
O(n^n), so it would be better to sort the thing first which takes O(n^42) and
binary search through the list which can be done in O(n*log(n!)). See the problem?

kind regards,

Jos

[pdeb1234]

i am not very sure about this but i think that>>>

log(n!)=log(n)+log(n-1)+log(n-2)+......+log(1);

so you have n operations each calculating a logarithm
hence the order is n multiplied by something.

On the other hand

nlog(n)=log(n^n)

again you have n terms.
so maybe that's why the question requires you to compare n! with n^n.

[JosAH]

Originally Posted by pdeb1234

i am not very sure about this but i think that>>>

log(n!)=log(n)+log(n-1)+log(n-2)+......+log(1);

so you have n operations each calculating a logarithm
hence the order is n multiplied by something.

On the other hand

nlog(n)=log(n^n)

again you have n terms.
so maybe that's why the question requires you to compare n! with n^n.

That reasoning is flawed; have a look at this:

2^n-1=2^(n-1)+2^(n-2)+2^(n-3)+ ... + 2^0

so there are n operations each calculating a power of two
but the order isn't n multiplied by something. It simply isn't true that if you have
an unkown function o(n) < f(n) (where f(n) is known) that the big-Oh of o(n) is O(f(n)).

kind regards,

Jos