Jump to content
  • Advertisement
Sign in to follow this  
cpp_boy

n*log(n) VS log(n!)

This topic is 4460 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I have invented a new sorting algorithm wich takes O(log n!) Is it much faster then O(nlogn). Maybe someone can draw those two functions in the same system for n~(1,10000) and post here the comparison picture.

Share this post


Link to post
Share on other sites
Advertisement
Heh. Sorry to burst your bubble, but by Stirling's approximation, O(n log n) = O(log n!). (This isn't surprising, since it has been proven that sorting based only on an ordering cannot be done in less than O(n log n) average.) If you like, post your algorithm and we'll try to figure out what it's called. (There are an immense amount of sorting algorithms; it's quite likely that yours is homomorphic to one which already exists.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Heh. Sorry to burst your bubble, but by Stirling's approximation, O(n log n) = O(log n!). (This isn't surprising, since it has been proven that sorting based only on an ordering cannot be done in less than O(n log n) average.) If you like, post your algorithm and we'll try to figure out what it's called. (There are an immense amount of sorting algorithms; it's quite likely that yours is homomorphic to one which already exists.)


Yes, but still, if you build graphs (in MS Excel for example) for those two,
log(n!) is MUCH faster than nlog(n). For example, for array sized 10000 the difference in number of operations requered is approximately 15,000 operations!!!
nlogn = logn + logn + ... + logn (n times)
log(n!) = log1 + log2 + ... + logn (n times)

As you can see, its much faster.
Am I wrong ???

Share this post


Link to post
Share on other sites
if you had read the link.
ln(n!) aprox = nln(n) - n
so, yes, as N gets bigger, your's seems faster in # of steps.
BUT, O notation drops the constants that do not affect the shape of the curve.
nlog(n) - n is O(nlogn)
n^2 + n + 1 is still O(n^2)
15*nln(n) + n^n is still O(n^n)

the point of O notation is to indicate the reletive growth rates of functions,
not the exact growth rate.
O(log(n!)) is therefore the same speed as O(nlog(n))

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran
if you had read the link.
ln(n!) aprox = nln(n) - n
so, yes, as N gets bigger, your's seems faster in # of steps.
BUT, O notation drops the constants that do not affect the shape of the curve.
nlog(n) - n is O(nlogn)
n^2 + n + 1 is still O(n^2)
15*nln(n) + n^n is still O(n^n)

the point of O notation is to indicate the reletive growth rates of functions,
not the exact growth rate.
O(log(n!)) is therefore the same speed as O(nlog(n))


I'm know very well what O notation means. But, in real life, 1 hour and 2 hours
are BIG difference. Therefore:

logn + logn + ... + logn (n times) = nlogn
log1 + log2 + ... + logn (n times) = log(n!)

doesnt take same time in real life. Take my algorithm, take quicksort, let them sort something. I dont care about O notation. If my alorithm takes 5 minutes less (for array sized 10^6 for example), I'll throw quick sort to the garbage!!!
One week and two weeks are the same O. Weach one you'll take ???


Share this post


Link to post
Share on other sites
You say you don't care for big-Oh notation, but the only thing we know about your algorithm is it's big-Oh complexity.

See this thread where a person also thought he had this smart new algorithm. Without any details we can't say your algorithm is slower than quick sort, but neither can we confirm it's not O(n^5)

Share this post


Link to post
Share on other sites
So. How about telling us about the algorithm so that we can verify that your claims are accurate? (More specifically to verify that your algorithm is correct, that your analysis of its complexity is accurate, and what its best/average/worst case behaviors are.)

[Edited by - Promit on May 1, 2006 10:14:02 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by cpp_boy
doesnt take same time in real life. Take my algorithm, take quicksort, let them sort something. I dont care about O notation. If my alorithm takes 5 minutes less (for array sized 10^6 for example), I'll throw quick sort to the garbage!!!

But what about arrays sized 10^10? Or bigger? Or what about for small N?
And what kind of arrays are you sorting on? Quicksort is O(n^2) in the worst case (which is when working on an almost sorted array, for example)

Quote:
One week and two weeks are the same O. Weach one you'll take ???

I'd take the one I can rely on to always give me good results.
If I have the choice between one that takes 1 or 2 weeks for *my* input? I won't sort, because someone else has obviously done it for me when benchmarking. [lol]

In other cases? Dunno, how do I know that yours is *always* faster? Or at least that it isn't noticeably slower?

Share this post


Link to post
Share on other sites
what does the exclaimation-mark in the O(log n!)-claim mean? factorial?

Share this post


Link to post
Share on other sites
Quote:
Original post by kusma
what does the exclaimation-mark in the O(log n!)-claim mean? factorial?

Yep.

Share this post


Link to post
Share on other sites

This topic is 4460 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!