Author: Martin Schubert
Date: 02:59:01 05/16/01
Go up one level in this thread
On May 15, 2001 at 21:50:35, Robert Hyatt wrote: >On May 15, 2001 at 18:04:28, Jesper Antonsson 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. >> >>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. > >As I said, real-world. The TSP problem is a real-world problem that is not >unbounded in size, simply because the number of cities in the world is finite >and countable. Chess may or may not be finite. The 50-move rule has not been >a part of the game forever. It is relatively recent. And within the past 20 >years it has been suspended for specific endings, and then later the suspension >was lifted. If we go back to prior-50-move-rule, the game is most certainly >infinite in any way you care to define infinite, for the real-world. There >is no way to search a tree to depth 1,000,000 for example. Not now. Not >ever. Never. Even if we know the game can be solved in that depth of >search. > >Yet the tree _still_ exhibits O(W^(D/2)) complexity for all D that I can reach >now, or that I will _ever_ be able to reach. To call this O(1) is nonsense. >Perhaps that is why theorists are somewhat useless? You are telling me that >as I increase D, the search time remains O(1), yet every time I do it, it >takes over 6X longer for the next search. One of those is wrong. I can prove >which with a simple program that I already have... > >O() does _perfectly_ at predicting the run-time of alpha/beta. For today. >For next Century. For time at the end of the universe. Each successive D >will multiply by roughly a factor of 6 the time for the previous D. And if >D happens to be limited, in some artificial way, but in a way that will never >affect the actual search, the so what? Big-Oh _still_ predicts the run-time >correctly in my model, not in the O(1) model... Therefore the O(1) model is >not only useless... it is worthless... Exactly. It's absolutly worthless. According to O-Notation it's not O(1). Anyone can define O-Notation differently. Than it's O(1). But that doesn't make sense. So this definition is rubbish. It doesn't help anywere. The O-Notation-definition helps. In mathematics often definitions look strange. But if you deal with them you'll recognize why it's defined the way it is defined. Because it makes sense. > > > >> >>>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. > >I am. It predicts the run-time of an algorithm. I've not varied from >that definition one iota. > >O(1) doesn't predict _anything_... > > > >> >>>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 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.