Author: Jesper Antonsson
Date: 16:17:36 05/13/01
Go up one level in this thread
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) 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. It's quite simple math, look it up.
This page took 0.05 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.