C
CBFalconer
^^^^Richard said:
??
F'ups set.
??
F'ups set.
P
Phil Carmody
CBFalconer said:^^^^
??
Set, followed, and had fun with.
extern volatile poster Chuck;
void Richard(post fromNick)
{
string s("W");
while(!Chuck.posted()) { s+="o"; }
s+="sh";
Chuck.respond(s);
}
Phil
J
James Kanze
Do you have any references on those, particularly with an
implementation? All I found for UMAC was a reference to book,
and Bob Jenkin's seems more concerned with cryptographic hashing
than anything else. If these are standard and widely used
algorithms for look-up hashing, I'd like to add them to my set
of hashing benchmarks.
(Note that cryptographic hashing and look-up hashing have very
different constraints, and a good hash function for one isn't
necessarily a good hash function for the other. Also, in
look-up hashing, speed counts. Taking 10 times more time to get
1% better distribution on the average is a loss.)
C
CBFalconer
Richard said:
Because, for example, if you pick an extreme position as the mark
for each phase, and the input array is either sorted or inversely
sorted, you will trigger that O(n*n) operation. With slight care
this becomes very rare. For any input array and any algorithm it
is possible to find an order that will trigger that worst case.
But they are rare.
J
Jerry Coffin
[email protected] says... said:
The most common implementation of Quicksort for arrays is unstable --
but a Quicksort on an array _can_ be written to be stable if you want to
badly enough, and for a linked list, it's quite easy to make it stable.
K
Kai-Uwe Bux
Jerry said:
My linguistic intuitions differ: Quicksort _is_ the algorithm published as
Algorithm 64 (and 63) by C.A.R. Hoare in the Communications of the ACM.
That algorithm sorts a sequence in place and is not stable. It makes
2n*log(n) comparisons on average and (1/3)n*log(n) exchanges on average.
Anything that is stable or deals with linked lists is an implementation of
a _different_ algorithm (and probably has different average complexities).
I am not saying that there are no refinements or other algorithms based on
similar ideas. Some of these algorithms are stable and some apply to linked
lists. Also, I am not a native speaker of English. Nonetheless, I feel that
algorithms have a certain identity (which makes it meaningfull to say that
a certain sorting algorithm is stable); and that implementations of an
algorithm must preserve that identity and the associated characteristics to
count as implementations _of_ that algorithm.
Best
Kai-Uwe Bux
J
Juha Nieminen
Kai-Uwe Bux said:
You talk about the big-O notation as some kind of generic function
which describes some asymptotic behavior of an algorithm. Basically you
are implying that the big-O notation could be used to describe *any*
asymptotic behavior of an algorithm. In other words, you could say
something like "insertion sort is O(n) in the best case".
If that is what you mean, then you will have a hard time explaining
what's the difference between the big-O notation, the big-Omega notation
and the big-Theta notation.
Where the big-O notation denotes the upper bound of the asymptotic
behavior of an algorithm, the big-Omega notation likewise denotes the
lower bound. In other words, the asymptotic behavior of an algorithm is
always between these two functions. For example insertion sort is O(n^2)
and Omega(n): Its worst case scenario performs quadratically with
respect to the size of the input, while its best case scenario behaves
linearly.
When the big-O and big-Omega functions for an algorithm are the same,
this can be expressed with the big-Theta function, which says exactly
that. In other words, it says that both the upper and the lower bounds
of the asymptotic behavior of the algorithm are the same. For example
merge sort is Theta(n lg n): It's O(n lg n) and Omega(n lg n).
You just can't say "quicksort is O(n lg n)" because that would be a
lie. The worst case scenario for quicksort is n^2, thus saying that it's
O(n lg n) is wrong.
AFAIK there's no widely established asymptotic notation for the
average behavior of a function, but if you want to express that, you'll
have to say it more verbosely. Sure, you can use a shortcut and say
"quicksort is O(n lg n) in average", but that would be technically
incorrect, or at least quite informal.
J
Juha Nieminen
CBFalconer said:
The purpose of the big-O notation is not to tell how well an algorithm
behaves in average or in most cases. It's a pure upper bound to the
asymptotic behavior of the algorithm.
Of course if we get completely technical, the big-O notation assumes
that the input can have any size. If you put an upper limit to the size
of the input (for example an amount relative to the amount of memory
addressable by the CPU, eg. 2^64 bytes), all algorithms which end at
some point (ie. don't go into an infinite loop) immediately become O(1).
Of course saying "all terminating algorithms are O(1) in my computer"
is not very informative, which is why it's always implicitly assumed
that there is no set limit.
J
Juha Nieminen
Kai-Uwe Bux said:
Why? Although it's a surprisingly common misconception that quicksort
requires random access, it doesn't. Quicksort is implemented in terms of
purely linear traversals of the array. Thus it's perfectly possible to
implement the *exact* same algorithm for a doubly-linked list (which can
be traversed forwards and backwards).
J
Juha Nieminen
Richard said:
No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.
The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.
If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?
J
Juha Nieminen
James said:
I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.
A
Andre Kostur
Not necessarily true. The big-O could refer to best-case, average, worst-
case, or anything in between. You just need to specify it. As I recall,
quicksort is O(n lg n) in the average case, O(n^2) worst case. Both say
something interesting about the algorithm.
J
Juha Nieminen
Andre said:
While you can say that colloquially, it's formally quite shaky.
In computational complexity theory big-O is not a generic notation
used to describe some asymptotic behavior of an algorithm. It's used to
specify an upper bound to the asymptotic behavior of an algorithm.
Saying, for example, "insertion sort is O(2^n)" is completely valid.
O(n^100) is equally valid. The big-O notation does not even require for
the upper bound to be tight. Any upper bound is valid as long as the
algorithm never behaves slower than that. However, saying "insertion
sort is O(n)" is not valid because with some inputs insertion sort
performs asymptotically more steps than that.
Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.
Likewise the big-Omega notation is used to set a lower bound to the
asymptotic behavior of an algorithm. For example if you say "insertion
sort is Omega(n)", you are telling that insertion sort never performs
less steps than an amount linearly relative to the size of the input.
Saying "the best case for insertion sort is O(n)" is exactly as silly
as saying "the worst case for insertion sort is Omega(n^2)". They don't
make sense as bounds in these sentences. They are misused to describe
some special cases.
B
Ben Bacarisse
Juha Nieminen said:
Yes one can do that, if you specify all the terms. I don't know why
one would, but it is certainly possible.
I can't see the problem. These notions express facts about functions
-- specifically membership of certain equivalence classes. If the
functions are properly defined, then so are the classes to which they
belong.
Using this terminology will cause trouble. In fact it may be the main
cause of the trouble. First. Big-O gives *an* upper bound, not *the*
upper bound (and certainly not the least upper bound). Secondly, you
can't apply the notation to an algorithm, only to some function
derived from the algorithm.
I get the feeling that you don't like it when that function is "the
average time taken over all possible inputs of size N" but that
measure is often useful. That function, for Quicksort, is O(n log n)
when all the details are formalised.
This is not helpful. Its time complexity is also O(n^3) and Omega(1).
You can't talk about an algorithm's big-O and big-Omega. Even if the
quantity in question is specified (e.g. worst-case time, average
space used, and so on) every algorithm has an unlimited number of
big-O bounds on that quantity.
But the time complexity for merge sort is also O(n^2). The key fact
is that if the function in question (say "longest time taken for data
of size N") is both O(f) and Omega(f) we say it is Theta(f). There is
no need to pretend that there is only one Big-O for the algorithm and
then go check if it is also the one and only Big-Omega for the
algorithm.
I agree, but did anyone say that (I have not checked)?
I disagree. I think the notion is well-defined and accepted by people
who study such things.
Saying "quicksort is O(n lg n) in average" is certainly very informal,
but so it saying that is "is O(n^2)". Both can be properly formalised.
T
Tim Rentsch
Juha Nieminen said:
Are you sure you understand what the term "stable" means for
sort algorithms, and why Quicksort isn't stable? The various
Quicksort algorithms I'm familiar with simply are not stable,
regardless of whether the elements to be sorted are held in
an array or in a doubly linked list.
T
Tim Rentsch
Juha Nieminen said:
http://en.wikipedia.org/wiki/Big_O_notation
Big-O notation is used to describe the asymptotic behavior of
functions, not algorithms. The worst case run time of an
algorithm, in terms of the size of its input, is one such
function; the average case run time of an algorithm is
another such function. Informally people say things like
"a bubble sort is O(n**2)", but really what is O(n**2)
is a function giving the running time of the algorithm,
not the algorithm itself.
R
Richard Tobin
Juha Nieminen said:
I think you are conflating two different upper bounds here. If we say
the function f(n) is O(n) is we mean that there is a k such that
|f(n)| <= kn for sufficiently large n. That is, kn bounds f(n) over
the range of sufficiently large n.
When we apply this to sort algorithms, what is the function f? It
might be the worst-case time to sort a set of size n, or the average
time. So it's perfectly reasonable to say that quicksort is
O(n log(n)) on average and O(n^2) in the worst case, meaning that the
average time to sort a set of n elements is O(n log(n)) and the
worst-case time is O(n^2).
Or f might be the time to sort a set S, in which case we can say that
it is O(|S|^2), since now we are taking a bound over all the sets.
If we implicitly take n to be |S|, we can reasonably say that quicksort
is O(n^2).
-- Richard
A
Antoninus Twink
He is *so* misinformed and *so* dogmatic that he might decide that the
Wikipedia article is wrong and he's right, and vandalize the article.
It might be worth keeping an eye on it.
P
Phil Carmody
Juha Nieminen said:
There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).
Phil
C
CBFalconer
Ben said:
Not so. It is O(nLOGn). Yes, you can disturb it into an O(n*n)
function, but that is abnormal. Mergesort is also stable and
requires no added memory.