Time Complexity Question (Big Oh) | Newbie | | Join Date: Oct 2008
Posts: 1
| | |
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
|  | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: Time Complexity Question (Big Oh)
Have a look at Stirling's approximation for n!.
kind regards,
Jos
|  | Moderator | | Join Date: Oct 2006 Location: New York, United States of America
Posts: 3,428
| | | re: Time Complexity Question (Big Oh)
You can also use the fact that n! < n^n, and solve O(log(n^n)).
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: Time Complexity Question (Big Oh)
Quote:
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
| | Moderator | | Join Date: Oct 2006 Location: New York, United States of America
Posts: 3,428
| | | re: Time Complexity Question (Big Oh)
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.
| | Expert | | Join Date: Sep 2007
Posts: 856
| | | re: Time Complexity Question (Big Oh)
Quote:
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).
| | Lives Here | | Join Date: Sep 2006
Posts: 12,070
| | | re: Time Complexity Question (Big Oh)
None of you guys noticed that this is not really a Java question at all?
kind regards
r035198x(<--Non-mathematician surrounded by mathematicians)
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: Time Complexity Question (Big Oh)
Quote:
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
| | Expert | | Join Date: Sep 2007
Posts: 856
| | | re: Time Complexity Question (Big Oh)
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.
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: Time Complexity Question (Big Oh)
Quote:
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
| | Newbie | | Join Date: Oct 2008
Posts: 4
| | | re: Time Complexity Question (Big Oh)
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.
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: Time Complexity Question (Big Oh)
Quote:
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
|  |
| | |  /bytes/about
We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights.
Get the best answers to your questions from over 226,471 network members.
|
