Author: Robert Hyatt
Date: 12:51:29 05/14/01
Go up one level in this thread
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.
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.