Author: Jeremiah Penery
Date: 18:42:11 05/09/01
Go up one level in this thread
On May 09, 2001 at 17:10:44, Ricardo Gibert wrote: >On May 09, 2001 at 15:11:41, Eugene Nalimov wrote: > >>Ok, here is simple example: let's consider sorting but limit the input by (a) >>limiting # of digits in each number (e.g. 1024 bits), and (b) limiting # of >>elements in the sequence we want to sort (e.g. max 10**40 elements). Yes, >>theoretical # of operations that are necessary to sort such a sequence is >>limited. But, nevertheless, you still can say that > > >Of course you can by generalizing the problem. You assume n is unbounded and >proceed, which you do very nicely (implicitly). > > >>* insertion sort is O(N*N), >>* quick sort is O(N*ln(N)) on average, but O(N*N) in the worst case, >>* heap sort is O(N*ln(N)) in the worst case. > > >If you *define your problem* in such a way that n is some *bounded* value (as it >is in chess), then the above is not correct. if n is bounded, then I can write a >sort routine containing a finite number of steps that is O(1). It won't contain >any loops and consist of a series of if-then statements and swaps and that's it. >That is clearly O(1). The routine will always execute *within* the same amount >of time. And this is _exactly_ why chess is _currently_ *NOT* O(1). WE DO NOT HAVE SUCH AN ALGORITHM FOR CHESS! Maybe one exists. Maybe one day, we can truly say that Chess is O(1). But in _all_ of today's chess programs, the problem is O(exp(n)) because they use a recursive (or iterative) tree-search, starting from depth 1 and successively searching deeper until time runs out. O(f(n)) has nothing to do with the potential size of the input. The f(n) serves to put a bound on *how changes of N affect the running time of the algorithm*.
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.