Author: Jesper Antonsson
Date: 15:04:28 05/15/01
Go up one level in this thread
On May 15, 2001 at 13:02:11, Robert Hyatt wrote: >On May 15, 2001 at 11:54:10, David Rasmussen wrote: > >>On May 15, 2001 at 06:35:42, Martin Schubert wrote: >> >>> >>>O(...) is about asymptotical behaviour. If n is bounded, it doesn't make sense >>>to talk about asymptotical behaviour. >>> >>>Martin >> >>Exactly. > > >not exactly. O(n) discussions can be asymptotical in nature, if the "bound" >is large enough to be considered infinite. > >IE I am _still_ waiting for someone to post a problem description (real-word >problem) that is unbounded in any way. To date, no one has. Which means all >real-world problems are O(1) and that definition is _still_ worthless and >pointless. Nonsense. This is a theory discussion and I don't give a rats ass about "real-world" problems. In chess, when you go above a certain depth, the time taken for the algorithm to complete doesn't increase. In the travelling salesman problem, for example, another city always increase the time taken for the algorithm to complete. That's why chess is O(1) and the TSP is not. >Big-Oh is _still_ a conceptual way to predict program run-time as the input >is increased in some way. I posted a direct quote from one theory book >yesterday. I can post others that make the same statement... You also quoted a definition. Use it. >In "theory" this "asymptotic behavior" might make sense. In practical terms, >it does not, and all the complexity analysis of algorithms, for any real-world >algorithm you name, must be of O(1) which is nonsense to those of us that are >working on algorithms. Yes, I agree, that's nonsense.
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.