Author: Martin Schubert
Date: 03:40:58 05/15/01
Go up one level in this thread
On May 14, 2001 at 15:51:29, Robert Hyatt wrote:
>On May 14, 2001 at 15:05:27, Uri Blass wrote:
>
>>On May 14, 2001 at 13:58:50, Robert Hyatt wrote:
>>
>><snipped>
>>>As far as the "mythical" requirement that N be unbounded, I give this explicit
>>>definition of Big-oh:
>>>
>>>"We say a function g(n) is O(f(n)) for another f(n) if there exist constants
>>>c and N such that for all n>=N, we have g(n) <= cf(n).
>>>
>>>I don't see any _requirement_ that n or N be unbounded.
>>
>>
>>
>>
>>If n is bounded and gets only a finite number of values then it is clear that
>>always g(n) is O(1) by this definition
>>
>>In this case g(n) can get only a finite number of values and
>>you can define c=max({g(n)}
>>You get g(n)<=c for all n>=1 and it means by definition that g(n)=O(1).
>>
>>Uri
>
>That is simply an interpretation. As I said, give me a citation that _requires_
>that N be unbounded. Since no _real_ algorithm can have unbounded input. The
>traveling salesman problem is one example. If we define a city as the space
>occupied by 1 atom, which is the smallest "city" of interest, then that is
>O(1), yet it is not given as O(1) in any book I have...
>
>Since by definition _all_ algorithms have finite input to be useful, they are
>all O(1) by this perverted definition. Perhaps math people define this
>differently, but in computational science, we don't consider _all_ algorithms
>to be O(1) as that definition is useless in the extreme.
O-Notation is never about one specific problem, it's about one "family" of
problems. If you want to look at the asymptotical behaviour of chess, you need
an input n, for example the size of the board. Other things don't make sense.
You can't say, something is O(1) because of something is bounded. First you have
to define what your "n" is, and then look at the asymptotical behaviour.
It doesn't matter for example, if you play chess only on a 8x8-board. The
question is "what would happen if you played on a nxn-board?".
Martin
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.