Author: David Rasmussen
Date: 00:41:16 05/16/01
Go up one level in this thread
On May 15, 2001 at 18:52:10, Dann Corbit wrote: >On May 15, 2001 at 18:14:05, David Rasmussen wrote: >[snip] >>Well, several textbooks disagree with you in Big-O not being about asymptotic >>behavior, but I'm to tired to go into that now, as I'm sure you know what I >>mean, and that we basically do not disagree. Do you want me to elaborate? > >The big-O notation is used to describe how an algorithm performs as n grows >large. What large means is purely a function of what the big-O type is. > >If q(n) is O(exp(n)), then "large" is a small number. 50 is unthinkable, for >instance. > >If q(n) is O(log(log(n))), then "large" is an enourmous number. One quintillion >is not a problem in the slightest, for instance. > >I think everyone really knows what everybody means by now. We seem to be >quibbling about semantics but when it boils down to it -- we all know where >everyone else is coming from (I think). Or at least we ought to. > >I think everyone has valid points. It is hard for me to imagine pure math uses >for big-O, but then again, my degree was in applied math. >;-) Big-O notation is very precisely defined. There is no need for all these informal agruments, and for using vague concepts like "small" and "large". And there's no need for Bob to argue that even if chess is O(1), the constant we're talking about is nearly infinite, so it will be the same in practice as if it was exponential etc. An excellent book on the subject is "Introduction to algorithms" by Cormen, Leiserson and Rivest. This book is a 1200 page brick with a solid mathematic foundation and a consistent and precise definition and usage of big-O (and little-O and Omega) notation. If you asked the authors of this book about the complexity of algorithms to solve chess, they would say that the ones we know today, were exponential. So would all other books, like D.E. Knuth's and others. You simply can't say "chess is O(1)". The terminology cannot be applied to problems, but to algorithms for solving problems, or for space requirements during problem solving, or any other parameter that is coupled with time in some way in any system.
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.