Author: Ricardo Gibert
Date: 14:32:27 05/09/01
Go up one level in this thread
On May 09, 2001 at 16:15:44, Dann Corbit wrote: >On May 09, 2001 at 16:10:09, Andrew Dados wrote: >[snip] >>Guaranteed fixed number of steps means O(1) afik. > >The number of steps to solve is a property of the algorithm. All algorithms >terminate after a fixed number of steps. That't part of the definition of the >term 'algorithm.' By fixed, he means constant. All algorithms terminate in a finite number of steps, but do not terminiate in constant number of steps. The difference is that an O(1) algorithm is guaranteed to finish in a finite number of steps fewer than some constant c. If it is more than O(1), the number of steps continues to be finite, but no constant c exists that delimits the number of steps executed. > >If any algorithm does not terminate in a fixed number of steps, then *by >definition* is ISN'T and algorithm. > >Therefore, we KNOW that the algorithm will terminate (perhaps in arbitrary >time). If we want to estimate how long it will take, we need to know the big-O >behavior of the algorithm. To call chess O(1) is simply not useful.
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.