Author: Dann Corbit
Date: 10:20:32 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:07:20, Ricardo Gibert wrote:
>On May 09, 2001 at 11:27:46, Dann Corbit wrote:
>
>>On May 09, 2001 at 10:12:30, Ricardo Gibert wrote:
>>
>>>On May 09, 2001 at 02:00:25, Dann Corbit wrote:
>>>
>>>>For those of you who don't want to perform your own web search, just choose one
>>>>of these:
>>>>
>>>>http://hissa.nist.gov/dads/HTML/bigOnotation.html
"or the algorithm will always be too slow on a big enough input"
>>>>http://bio5495.wustl.edu/textbook-html/node15.html
>>>>http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html
"whether this particular problem of size is a hard case or an easy case for our
algorithm to solve"
>>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html
"The Size of a Problem
Big-O notation is used to express an ordering property among functions. In the
context of our study of algorithms, the functions are the amount of resources
consumed by an algorithm when the algorithm is executed. This function is
usually denoted T(N). T(N) is the amount of the resource (usually time or the
count of some specific operation) consumed when the input to the algorithm is of
size N."
>>>>http://classes.monterey.edu/CST/CST338-01/world/BigO.html
"In determining the efficiency of an algorithm, we are interested how the
problem scales as the size of this characteristic number grows."
>>>>http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O
"It may seem odd, but two positive real valued functions on N can each be big-O
of the other, and such pairs of functions are considered roughly EQUIVALENT --
in mathematical parlance, "ASYMPTOTICALLY PROPORTIONATE". f is big-O of g if and
only if
f(n) < [C*g(n)] whenever n > m,
for some positive constants m and C. This is true if and only if
f(n)/g(n) < C whenever n > m,
and if and only if
g(n)/f(n) > 1/C when n > m.
On the other hand, if g is big-O of f, then for some positive K and r,
g(a) < [K*f(a)] whenever a > r,
and this is the same as
g(a)/f(a) < K, and f(a)/g(a) > 1/K.
So
C > f(s)/g(s) > 1/K
whenever s is greater than both m and r. If f(s)/g(s) was a constant, not
depending at all on s, then we would say that f and g are proportionate. The
last inequality above shows that the ratio of f(s) to g(s), while quite possibly
not a constant, does become "trapped" between C and 1/K for large enough values
of s. This phenomenon is called "asymptotic proportionality". We think of the
two functions as being "roughly proportionate"."
>>>>
>>>>CS:201, FCOL!
>>>
>>>Big-O notation is used to describe asymtotic behavior. It commonly used to
>>>describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is
>>>understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets
>>>confused with infinity. This is an error, but let's not get into that. It isn't
>>>relevant here)
>>>
>>>In chess, n in is bounded. This is a critical distinction, that means chess is
>>>*not* NP.
>>
>>GREAT! Then it's computable. What's the answer, win-loss-draw?
>>;-)
>>
>>>If we were to allow the size of the chessboard to expand, then the
>>>number of steps in its solution would be NP (extremely likely, but not certain!)
>>
>>{Not you too!}
>>
>>WHAT UTTER POPPYCOCK. Please provide a citation from a reputable source that
>>says if we have a bound on the data our algorithm becomes O(1).
>
>In all the definitions you refer to in the links you gave, n is clearly given as
>unbounded.
>
>The notation O(f(n)) is used to describe the asymptotic behavior for
>sufficiently large n as n increases. This is crystal clear from the citations
>You give above.
>
>It makes no sense to speak of the asymptotic behavior of an algorithm as n
>increases when n is in fact constant as it is in chess.
>
>That's so
>>nonesensical that it renders an analysis of algorithsm as completely pointless.
>>ALL INPUTS ARE BOUNDED!!!!!
>
>Of course they are bounded in a specific instantiation of a problem where n is
>unbounded, but they are not bounded (at least in theory) before the problem is
>instantiated.
>
>>
>>There is no such requirement anywhere in the literature. The running time of
>>the algorithm can be discerned by examination of the algorithm alone. In fact,
>>that is how it is always done.
>>
>
>Read and understand the very citations you give above more carefully.
>
>[snip]
>
>If I want to find the maximum of 2 integers, I can give an algorithm that is
>O(1). This means I can furnish a finite program that does not contain any loops
>that will accomplish the task.
>
>If I generalize this problem to n integers, where n is unbounded, then I must
>resort to using a loop. The algorithm is then O(n). If n is bounded then I can
>write the program without any loops, since I know n <= some constant. The
>algorithm is then O(1).
>
>In chess, n is bounded. I can write a finite program (in theory I can) that does
>not contain any loops. The running time is O(1). If n is unbounded, no such
>program without loops exists, so instead if I use minimax, the running time is
>O(exp(n)).
>
>This is all very clear from the citations you give. Please read carefully.
You are right that one of us has a serious comprehension problem.
This page took 0 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.