Author: Robert Hyatt
Date: 10:58:50 05/14/01
Go up one level in this thread
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: "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. 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." So I don't see how anyone can say "The O notation does not have a point." Every book I have gives this "point". 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...
This page took 0.06 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.