response 6 of 22:

Apr 21 15:26 UTC 1999

Sure would like to have a mint-condition woodla, but I sure don't think 
there's much chance I'm going to get one from remmers.

response 8 of 22:

Apr 27 07:54 UTC 1999

It's not 0(1) but O(1) - and it's the mathematicians short-hand way of
writing down "order 1", which is one measure of the speed of an
algorithm.  The speed of any algorithm can be expressed as a function of
"n" (where "n" is the number of items being processed).  That function
can normally be written as the sum of simplier functions of n.  As n
becomes very large, typically one of these subfunctions or terms becomes
dominant (much larger than all the other terms combined), and so one can
closely approximate the running time of the function by simply measuring
this one term.  This term is very often the product of a positive
constant and n to some power, so it is traditional to ignore the
constant and say O(n^2), if the performance of the algorithm is nearly
proportional to the square of the number of items involved given a large
# of items.  O(1) means that the algorithm always takes the same amount
of time when processing a large # of items, which means that given a
large enough # of items, such an algorithm will beat out anything based
on O(n^2), for instance.  Of course, this is not the whole story - for
instance, for small and medium numbers of items, the O(n^2) algorithm
might have less setup time than the O(1) algorithm, and might still be a
winner.  There is also the possibility that the O(1) algorithm is not
well-behaved for small values of n and either takes much longer than for
large values of n, or perhaps worse yet, isn't computable in a finite
amount of time.

response 10 of 22:

Apr 27 19:01 UTC 1999

A linear algorithm would be O(n).  O(f) (pronounced "Big Oh of f") is the
"order" of a function f.  In general the definition says that

    f is O(g) if there are constants A and B such that
    A|g(n)| <= |f(n)| <= B|g(n)| for all but finitely many values of n.
    (|x| is the absolute value of x.)

So for instance, a bubble sort makes n(n-1) comparisons and some lesser number
S(n) of swaps in the process of sorting n items.  So the time it takes to run
is
    f(n) = cn(n-1) + sS(n)
where c is the time it takes to do a comparison and s is the time it takes
to do a swap.  Since
    (c/2)n^2 <= f(n) <= (c+s)n^2
for all but finitely many n, f is O(n^2).  So you can say that a bubble
sort runs in O(n^2) time.

response 12 of 22:

Apr 27 22:25 UTC 1999

Re resp:8 - Sorry, I'm reading this on a library Mac, and in the font it
chose, I can't tell the difference between O and 0, unless they are right next
to each other (and then barely).

response 14 of 22:

Apr 28 13:25 UTC 1999

(By Jiminny - Marcus appears to have figured it out!)

response 16 of 22:

Apr 30 21:34 UTC 1999

What's a woodla ?!??

response 18 of 22:

May 4 20:05 UTC 1999

differnet - and better - font. DEAL WITH IT.