Author: Dann Corbit
Date: 15:13:15 05/09/01
Go up one level in this thread
On May 09, 2001 at 17:58:08, Uri Blass wrote: >The definition that I remember from university for O(1) is: > >f(n) is O(1) if there is a constant C such that |f(n)|<C for every finite n. >(|f(n)| is the absulute value of f(n)). > >We learn from this definition that if n is bounded then f(n) is O(1) because you >can choose C=1+max(|f(1)|,|f(2)...|f(n)|) > >An algorithm that help to solve only one problem that can be solved in a finite >time is always O(1) by this definition. >An algorithm that helps to solve a finite set of problems that everyone of them >can be solved in a finite time is also O(1) by this definition. > >1)If you look at the problems search to depth n in chess then there is only a >finite number of problems because searching to depth 9^(9^9) gives the same >result as searching to depth 9^(9^9)+1 even without the 50 move rule. > >Conclusion:Searching to depth n in chess is O(1). > > >2)I will explain the reason that sorting is not O(1) (The number of elements is >bounded from the computer's point of view but I am not looking at it from a >computer point of view) > >You can look at sorting(not from computer's point of view) as an infinite number >of problems(sorting 1 element,sorting 2 elements....) when everyone of them can >be solved in a finite time but the input is not bounded. > >You have no constant C such that every one of the problems can be solved in less >than C units of time. Not only is that not correct, but I detailed examples. For instance, in the ANSI C99 language, the highest precision counting type that can be relied upon is unsigned long long. Hence, the maximum possible time to sort a vector via comparison is O(n*(log((2^64-1)!)) which is a constant. >3)You can say that the definition of O(1) is not important and we never have an >infinite number of problems so practically n is bounded. >The reason that people are interested in non existing cases that n is not >bounded is the fact that we can learn from them about cases when n is bounded >but the bound is very big. > >You can say that in chess the bound is big enough to look at it as not O(1) from >a practical point of view. > >If people are going to say "not O(1) from a practical point of view" instead of >"not O(1)" then I am not going to argue against them. Consult any text on algorithm complexity. Chess will be listed as an NP problem along with TSP, etc. Your definition has no value. The correct definition can be used to calculate the next level of the tree.
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.