Author: Uri Blass
Date: 14:58:08 05/09/01
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. 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. Uri
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.