Author: Dann Corbit
Date: 16:27:07 05/09/01
Go up one level in this thread
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)? >> >>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.23 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.