Author: Ricardo Gibert
Date: 16:31:32 05/09/01
Go up one level in this thread
On May 09, 2001 at 19:27:07, Dann Corbit wrote: >On May 09, 2001 at 19:23:45, Ricardo Gibert wrote: >>On May 09, 2001 at 18:16:48, Dann Corbit wrote: >>>Some people are insisting that finite inputs mean O(1). >>> >>>My insistence is that the big-O behavior should model the difference from n to >>>n+1 and from n to n-1 (past some point n0). >> >>Definition: f(n) = O(g(n)) (read as "f of n equals big oh of g of n") iff there >>exists two positive constants c and n_0 sth |f(n)| <= c*|g(n)| for all n >= n_0. >> >>I see nothing in the above definition that talks about "n to n+1 and from n to >>n-1". >> >>I do see that n is unbounded. I also note that in chess, n *is* bounded unless >>you generalize 8*8 chess to n*n chess when n is then unbounded. If you make such >>a generalization, you can conclude that n*n chess is O(exp(n)). You can then >>instantiate it to the 8*8 case to obtain a usable result, but please do not say >>that 8*8 chess is O(exp(n)) rather than say n*n chess is O(exp(n)). >>I don't see this can be made more clear. I'm really at a loss as to why you >>cannot interpret formal definitions correctly. > >If someone pays you to give an algorithm analysis of chess will you really >report that it is O(1)? Yes and I will point to the access of Nalimov EGTBs as an example of such an algorithm. I will observe that in principle 5-man EGTBs can be extended to 32-man EGTBS, though this has no practical significance. > >>> >>>There are no real algorithms with infinite inputs. These so-called algorithms >>>can never terminate. >> >>I never said anything about infinite inputs. "Unbounded" is not the same as >>"infinite". Get the terminology straight or you will get nowhere. > >When analyzing algorithms, we do make assumptions about data types and ranges. >Otherwise, the task of analysis itself is impossible.
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.