Sign in to follow this  
cpp_boy

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

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
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
Some here said that O(log n!) is approximetaly O(nlogn - n)
For ANY input, (nlogn - n) is faster than (nlogn).

In its best case, my algorithm takes O(n). Worst case is O(log n!) .
So, in any case, I didnt heard about anything faster than this one.

One bad thing about my algorithm, is that it requeres a kind of linked list, and this one takes a little extra memory.

Unfortunelly, at this moment, I cannot post my algorithm here.
First of all, I want to show it to my university professor.

Share this post


Link to post
Share on other sites
Quote:
Original post by cpp_boy
Unfortunelly, at this moment, I cannot post my algorithm here.
Why not?

Share this post


Link to post
Share on other sites
a) O(log(n!)) = O(nlog(n) - n) = O(nlog(n))
b) log(n!) aprox = nlog(n) - n

BIG DIFFERENCE

sorry. I feel the need to clarify your notation. No argument as to the speed.
But you keep using O() notation. O() notation covers a class of functions.
All O(nlog(n)) functions are not the same speed. There are lots of sorting functions
that beat qsort for some inputs.

I'm not arguing that your sort is the same speed as qsort. But you keep trying to make the notation say something
it isn't ever going to say. As far as you have said:
the best case is xN, the worst case is xlog(n!).
So, likely you beat the best case of sort, and didn't hit the xN^2 worst case of qsort.

Like others have said, you may have re-discovered another sorting algo. or actually come up with something new.

What type of benchmarks have you done? sorted, partially sorted, totally random, reverse sorted, all the same element?

If you really have done extensive benchmarking, I hope to see what you have done after you have who-ever look over it.
There is a chance you have something that could be good in some applications.

Share this post


Link to post
Share on other sites
It might be a good idea to post your algorithm here before presenting it, because there is a non-zero chance (mildly put) that it is a variation of an already known algorithm. Noone will try to 'steal' your algorithm (if anything, you'll help the programming community if you have made a real breakthrough).

I have a small benchmark written in C sitting in my computer, which times several sorting algorithms and prints the results. I could run some benchmarks for you if you are interested.

Share this post


Link to post
Share on other sites
Quote:
Original post by cpp_boy
Some here said that O(log n!) is approximetaly O(nlogn - n)
For ANY input, (nlogn - n) is faster than (nlogn).


Dispite your claims, you do not understand O notation. O(nlogn -n) equals O(nlogn). Really it does. They are the same set.

QuickSort is an O(n log n - n) function. QuickSort is an O(log n!) function. All O(nlogn) functions are O(logn!) functions.

O(nlog(n)) is a set of functions.
O(log n!) is a set of functions.
As it happens
O(nlog(n)) is the same set as O(log n!)

In other words, there is a K and C such that for sufficiently large N, for all n>N:
K nlog(n) < log(n!) < C nlog(n)

So, based off the knowledge that your search algorithm is O(log n!), no conclusion about it's relative performance compared to standard search algorithms can be made.

I'm not saying your algorithm is faster or slower than other functions. I'm saying that your function being O(logn!) doesn't tell you anything at all about the relative speed of your function compared to other search functions.

Oh, and beware the Turning tarpit. Just because two things are equivilent does not make them the same.

Share this post


Link to post
Share on other sites
I suppose a more layman's way of saying the same thing, is that Big-O notation "gets rid of" lower-order terms and terms that have a diminishing relative effect as n tends toward infinity. For instance, for some polynomial xn + xn-1 + xn-2 + ... + x2 + x1, Big-O notation would classify this as O(xn), without regard to the other terms. So the "real" polynomial associated with that complexity could have been the polynomial I posted, or maybe it was just xn. The idea is you don't know, so it makes no sense to compare complexities in that way and say that one is faster than another, because you have no idea what other terms used to be there but were "discarded" because of the Big-O.

Share this post


Link to post
Share on other sites
I know perfectly well what is O, Theta, and Omega notations.
But still. The average of my algorithm is somewhere between n And log(n!) .
And this is realy fast. It beats merge and quick in any possible case !!!

Share this post


Link to post
Share on other sites
If your algorithm determines the order of sorting by pairwise comparison (as the majority of algorithms, such as quick sort and merge sort do) then it can't be better than O(n log(n)). If not then you may have something similar to radix sort.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fiddler
It might be a good idea to post your algorithm here before presenting it, because there is a non-zero chance (mildly put) that it is a variation of an already known algorithm. Noone will try to 'steal' your algorithm (if anything, you'll help the programming community if you have made a real breakthrough).


I'd bet 3 to 1 odds that he shows this algorithm to his proffessor, gets told its real name, then never comes back to this thread.

Share this post


Link to post
Share on other sites
Quote:
Original post by cpp_boy
I know perfectly well what is O, Theta, and Omega notations.
But still. The average of my algorithm is somewhere between n And log(n!) .
And this is realy fast. It beats merge and quick in any possible case !!!


Natural merge sort in the best case is n and the worst nlog(n) so it has the same properties as your algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by Cocalus
Quote:
Original post by cpp_boy
I know perfectly well what is O, Theta, and Omega notations.
But still. The average of my algorithm is somewhere between n And log(n!) .
And this is realy fast. It beats merge and quick in any possible case !!!


Natural merge sort in the best case is n and the worst nlog(n) so it has the same properties as your algorithm.
And introsort manages the same performance as well.

Of course, there are tons of missing constants here that are of some relevance. Not only that the poster mentioned using linked lists, which almost certainly means the algorithm is pitifully heavy in cache misses. His constant factor is potentially massive.

Share this post


Link to post
Share on other sites
It's been a long time since we've seen a "my new algorithm is better than anything else, but I can't/won't tell you what it is -- you just have to believe me" thread.

They are entertaining. I kind of miss them.

Share this post


Link to post
Share on other sites
On average, no sort that can sort an arbitrary number of elements that can have an arbitrary number of values can be faster than O(n lg n).

It is possible to beat other sorts on the constants. It is also possible to have "more good cases", or at least "better good cases", that take sub-O(n lgn). But "most" of the sorts will be O(n lgn) or worse.

Note that the above requirements can give you faster searches.

For example, a search that is limited to a certain precision of float/int can be faster than O(n lgn). In particular, if there are "k" possible different values to your data you are sorting, you can do a sort in O(n) or O(n lg k) time and O(lg k) space -- linear time in n.

(A sort on 8 bit integers can be implemented as an array of counters. O(n) on the number of integers.)

Other tricks work when you are sorting other kinds of restricted datasets.

But, if I remember the proof right, if you find a sort that takes less than O(n lg n) time on the "average", you have proven that the theory of computation contains a contradiction, causing a huge shake up in the entire theory of knowledge, and you will become legendary mathematician on par with Russel, Taylor, Green, Turing or Godel.

Good luck with that. If you do become famous for all time, can I be a footnote? Pweeese?

Share this post


Link to post
Share on other sites
cpp_boy,

1) O(log n!) is the same as O(nlogn) so complexity will not reveal if your algorithm is faster or slower than all the other O(nlogn) algos.

2) you cant do better than that with comparing sorting, so dont come to your professor saying "I have a new sort that does better than O(nlogn)" or he will gently kick you out.

3) when comparing algorithms of the same complexity group there are other important "cross platform" issues ("cache friendliness" is very important and linked list isnt cache friendly at all)

4) even without the linked list, you most likely wont beat quicksort - simply because sorting algorithms has been studied and explored for dozens of years (more?) by thousands of very talented people - and they came to the conclusion of using quicksort. Do you believe you are better than all the thousands that came before you? Chances are your idea has been explored years ago.
If you want to find something new you better choose some newer less explored area such as game theory or parallel algorithms or such.

Share this post


Link to post
Share on other sites
The OP hasnt responded in quite a few posts now,
So I think we're all wasting our time
My bet is that he did a little research or talked with a proffessor, and found out that his idea isn't new. Thus isn't coming back.

no point in adding any more comments if he isn't listening, right?

unless of course it did turn out to be a new algorithm, in which case Please Explain it to us cpp_boy

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this