Author: Robert Hyatt
Date: 18:39:00 05/15/01
Go up one level in this thread
On May 15, 2001 at 19:29:24, Martin Schubert wrote: >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. >> >>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... >> >>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. > >Some algorithms sort in O(n*n), some in O(n*log n). You say the difference is >unimportant? Nope. You are mis-reading. I claim that every algorithm I use has some sort of complexity function. Minimax = O(W^D). Alpha/beta = O(W^(D/2)) and so forth. But some would say that if the size of the input is limited in any way, these algorithms are all O(1). I simply point out that there are no real-world problems without a limit on the size of the input, which means all problems are O(1) in that deranged model of things.
This page took 0 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.