Author: Dann Corbit
Date: 15:06:18 05/08/01
Go up one level in this thread
On May 08, 2001 at 17:28:07, Dan Andersson wrote:
>A bit of nitpicking, nothing serious.
>>All inputs into any computer program must be finite. Otherwise, the program
>>cannot ever terminate or even stop reading the input.
>Thats not strictly true your program might operate on a stream that might or
>might not terminate. And the algorithm should only need a finite subset to
>compute an output.
>
>>
>>O(f(N)) means that the time spent by the algorithm will always lie below some
>>constant times the function f() if N is large enough.
>The problem here is that the number of chess positions are finite.
>>
>>Chess is exponential (with all current algorithms). To argue otherwise is just
>>plain silly. Similarly for other NP-hard problems or problems of any nature.
>>
>>Consider sorting. We are not going to insert an infinite set into our sorting
>>algorithm. Even if we could magically sort in O(N) it will never terminate. So
>An interesting example.
>We might have a perfectly sorted list for every N by inserting the new number
>when it appears. And that has the following connection to solving chess: By
>using the Science-Fiction device that generates all legal (maybe not a necessary
>condition) chess positions we have to ask ourselves what is the lowest
>complexity function that proves the graph. Really interesting question, need to
>think hard on this. I'm only speculating now, too tired to think really, but
>Proof Set (Not number)search seems a good candidate for a solution attempt and
>if so the solution could be =< O(N^2) I think.
>>we are *ALWAYS* talking about finite inputs. The type of function determines
>>how large a value of N is feasible. Will you solve a chess tree of depth 5000?
>>No. Not now. Probably not ever. As in never-ever.
>>
>>Your arguments are absurd.
>
>Thanks for making me use my noggin'
Just to expound a bit...
Suppose we want to solve a matrix. Classic examples abound, and it is a well
known problem. The comlexity is (n^3) {yes, I know about Strassen -- that
doesn't change anything for TWO reasons).
You approach your boss:
"Well, it's going to be expensive to solve the matrix because it's an O(N^3)
algorithm."
The boss replies:
"Well, we have 400 thousand inputs."
You reply:
"Terrific! Since we have a fixed number of inputs, the solution is O(1)."
What's wrong with this picture?
Using the same reasoning chess is O(1), sorting is O(1), in fact, every problem
with an algorithm that should halt is O(1) given a fixed input. Wonderful news,
everything has suddenly become computable.
Clearly, there is something fishy going on. And what is it that smells like a
carp on the beach?
a program is O(f(N)) for some function f() for an input of size N. If f(N) is
N!, then the fact that our input is only 5000 does not suddenly render the
algorithm computable. Here is what it means, right from the horse's mouth...
{Cormen, Leiserson, and Rivest's "Introduction to Algorithms" on pages 26-27:
"The Theta notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation. For a given function
g(n), we denote O(g(n)) the set of functions
O(g(n)) = {f(n): there exists postive constants c and n0 such that
0<=f(n)<=c*g(n)) for all n >= n0}
We use O-notation to give an upper bound on a functoin, to within a constant
factor. Figure 2.1(b) shows the intuition behind O-notation. For all values n
to the right of n0, the value of the function f(n) is on or below g(n).
To indicate that a function f(n) is O(g(n)), we write f(n)=O(g(n)). Note that
f(n) = theat(g(n)) implies f(n) = O(g(n)), since theta-notation is a stronger
notion than O-notation. Written set-theoretically, we have Theta(g(n)) is a
struct subset {is contained in} O(g(n)). Thus, our proof that any quadratic
function an^2 + bn + c, where a>=0, is in theta(n^2) also shows that any
quadratic function is in O(n^2). What may be more surprising is that any linear
funcion an+b is in O(n^2), which is easily verified by taking c=a+|b| and n0 =
1.
Some readers who have seen O-notation before may find it strange that we should
write, for example, n = O(n^2). In the literature, O-notation is sometimes used
intofmally to describe asymptotically tight bounds, that is, what we have
defined using Theta-notation. In this book, however, when we write f(n) =
O(g(n)), we are merely claiming that some constant multiple of g(n) is an
asymptotic upper bound on f(n), with no claim about how tight an upper bound it
is. Distinguishing asymptotic upper bounds for asymptotically tight bounds has
now become standard in the algorithm literature.
Using O-notation, we can often describe the running time of an algorithm meremy
by inspecting the algorithm's overall structure. For example, the doubly nested
loop structure of hte intsertion sort algorithm from Chapter 1 immediately
yields an O(n^2) upper bound on worst case running time: the cost of the innter
loop is bounded from above by O(1){constant}, the indices i and j are bot at
most n, and the inner loop is exectued at most once for each of the n^2 pairs of
values for i and j.
Since O-notation describes an upper bound, when we use it to bound the
worst-case running time of an algorithm, by implication we also bound the
running time of the algorithm on arbitrary inputs as well. Thus, the O(n^2)
bound on worst case running time of insertion sort also applies to its running
time on every input. The Theta(n^2) bound on the worst-case runninbg time of
insertion sort, however, does not imply a Theta(n^2) bound on the running time
of insertion sort on every input. For example, we saw in Chapter 1 that when
the input is already sorted, insertion sort runs in Theta(n) time.
Technically, it is an abuse to say that the running time of insertion sort is
O(n^2), since for a given n, the actual running time depends on the particular
size of n. That is, the running time is not really a function of n. What we
mean when we say "the running time is O(n^2)" is that the worst-case running
time (which is a function of n) is O(n^2), or equivalently, no matter what
particular input of size n is chosen for each value of n, the running time on
that set of inputs is O(n^2)."
In the event that CLR is considered too elementary, here is Knuth's take on the
matter from TAOCP, volume 1, page 107:
"In general, the notation O(f(n)) may be used whenever f(n) is a function of the
positive integer nl it stands for a quantity that is not explicitly known,
except that its magnitude isn't too large. Every appearance of O(f(n)) mean
precisely this: There are positive constants M and n0 such that the number xn
represented by O(f(n)) satisfies the condition |xn| <= M|f(n)|, for all integers
n>= n0. We do not say what the constants M and n0 are, and indeed those
constants are usually different for each appearance of O."
HTH
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.