# 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.

## 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 on other sites
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 on other sites
Quote:
 Original post by SneftelHeh. 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 on other sites
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 on other sites
Quote:
 Original post by KulSeranif you had read the link.ln(n!) aprox = nln(n) - nso, 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 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 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 on other sites
Quote:
 Original post by cpp_boydoesnt 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 on other sites
what does the exclaimation-mark in the O(log n!)-claim mean? factorial?

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

Yep.

##### 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.

This topic is now closed to further replies.

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 29
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002289
×