n*log(n) VS log(n!)
Author
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.
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.)
Author
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 ???
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))
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))
Author
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 ???
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)
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)
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]
[Edited by - Promit on May 1, 2006 10:14:02 AM]
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?
Quote:Original post by kusma
what does the exclaimation-mark in the O(log n!)-claim mean? factorial?
Yep.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
