Author: Jesper Antonsson
Date: 14:52:07 05/15/01
Go up one level in this thread
On May 14, 2001 at 13:58:50, Robert Hyatt wrote: >On May 13, 2001 at 20:42:29, Jeremiah Penery wrote: > >>On May 13, 2001 at 19:17:36, Jesper Antonsson wrote: >> >>>On May 11, 2001 at 21:42:53, Jeremiah Penery wrote: >>> >>>>On May 11, 2001 at 16:43:38, Jesper Antonsson wrote: >>>> >>>>>My understanding of this topic is without a doubt as good or better than yours, >>>>>thank you very much. I agree that it is not meaningful to talk about complexity >>>>>for sorting 1000 items, while I don't agree that's comparable to chess. You, >>>>>however, doesn't seem to understand that *depth* was the input considered in the >>>>>start of this argument, and that *chess* is the topic. >>>> >>>>It seems you don't understand the point of the O-notation. It's not supposed to >>>>tell you that algorithm FOO takes time X to run on input BAR. It's supposed to >>>>let you _estimate_ the running time of algorithm FOO on input BAR+1 (BAR+2, >>>>BAR+3, etc...) when you know the running time on input BAR. ***You know that >>>>the algorithm will eventually complete, no matter what the input!*** But, for >>>>example, naming a sorting algorithm O(1) says that it will sort 1000000 numbers >>>>just as fast as it sorts 5 numbers. When you call a tree-searching algorithm >>>>O(1), when depth is the input, you're saying that it takes the same amount of >>>>time to search depth 500 as it does to search depth 3. Obviously, this is wrong >>>>for any chess program. >>> >>>This is all wrong, my friend. The "O-notation" doesn't have a "point" (or at >>>least not that one) > > >That is totally incorrect. From one of many books, "Introduction to Algorithms" >by Udi Manber: > >"The purpose of algorithm analysis is to predict the behavior, expecially >the running time, of an algorithm." > >As far as the "mythical" requirement that N be unbounded, I give this explicit >definition of Big-oh: Bob, you are dreaming. You keep repeating that "unbounded" nonsense, but at least I have never given that requirement. >"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). Exactly! Now when you have the definition in front of you, you should be able to easily see that chess is O(1). Why? Because when n>=5000 or whatever, g(n) <= c*1. (n is target depth, g(n) running time, c is a big constant) It isn't harder than that. >I don't see any _requirement_ that n or N be unbounded. The "for all n" only >says that the expression is valid for each n that is >= N. IE for large enough >n, >the function g(n) is nore more than a constant times the function f(n). The >function g(n) may be less than cf(n), even substantially less; the O notation >bounds it only from above." Yup. So chess is also O(2^n), but you repeatedly claimed that it *isn't* O(1), which is quite wrong, of course. >So I don't see how anyone can say "The O notation does not have a point." Every >book I have gives this "point". Of course, even definitions are made for a reason, but the O notation is old and it's definition carved in stone. You can't go around claiming things that opposes the definition because it doesn't fit you intuitive notion of whether the consequenses of that definition are useful or not in a particular case. > Nor do I see any requirement (yet) that says >that unless the size of the input is essentially without limit, O notation does >not apply. > > > >> >>Then why take the time to find the O(f(n)) of any algorithm? The point of doing >>it is so that you can see whether algorithm A will run faster than algorithm B >>(quicksort runs faster than bogosort, for example) with arbitrary input. If you >>have two sorting algorithms, one with O(n + 5000) and one with O(n!), you can >>say that for very small N, the O(n!) program will be faster, but otherwise it >>will be much slower. This is "point" of O(f(n)). If you don't correctly find >>O(f(n)) of an algorithm (or algorithms), how will you ever know which one to >>choose for a particular job? >> >>>and O(1) does not guarantee same running time for different >>>inputs. The O-notation is clearly defined, and my use adheres to the definition. >> >>O(1) is _constant_ running time, regardless of input length. You can make a >>graph and see this very clearly. Any algorithm with different running times for >>different N must use an O(f(n)) that actually has an "n" in it - O(n), >>O(log(n)), O(n*log(n)), O(n!), O(exp(n)), etc. >> >>>It's quite simple math, look it up. >> >>I agree, the math is quite simple. > > >Nobody is looking this up. Everyone is using their own personal interpretation >of something they were exposed to years ago. I am _still_ waiting on someone >to quote a book that _requires_ the number of inputs to be unlimited. And I >would hope that everyone knocks off the "O is not used to estimate run-time of >an algorithm" without quoting their source. I just quoted one of mine. I will >be happy to quote others if requested... You are fighting a straw man, Bob. We don't require the depth to be unlimited. It doesn't matter. Whether the depth is unlimited or not, chess is O(1). Just look at the definition you gave.
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.