Author: Dann Corbit
Date: 17:21:56 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:12:14, Ricardo Gibert wrote: >On May 09, 2001 at 20:05:24, Dann Corbit wrote: > >>On May 09, 2001 at 20:00:09, Peter McKenzie wrote: >> >>>On May 09, 2001 at 19:34:08, Dann Corbit wrote: >>> >>>>On May 09, 2001 at 19:31:32, Ricardo Gibert wrote: >>>>[snip] >>>>>>If someone pays you to give an algorithm analysis of chess will you really >>>>>>report that it is O(1)? >>>>> >>>>> >>>>>Yes and I will point to the access of Nalimov EGTBs as an example of such an >>>>>algorithm. I will observe that in principle 5-man EGTBs can be extended to >>>>>32-man EGTBS, though this has no practical significance. >>>> >>>>This is an incompetent assessment. 32 man EGTB's cannot even conceivably be >>>>attempted if half the universe were turned into computers and the other half >>>>computed madly until the power went out. >>> >>>Dan, it seems to me that Ricardo is presenting a logical argument here. I don't >>>think the argument is refuted by you calling it incompetent! >>> >>>Similarly, I don't see why the practical difficulties of constructing 32 man >>>EGTBs should detract from their theoretical existance. >> >>Because if you can't make one, it won't ever exist. > > >The definition of big-O does not include such considerations, so the definitions >proper application does not include it either. > >If you think the definition should be modified to include this, that's fine, but >do not pretend that the proper application of the definition as it actually >stands includes this. An analysis of algorithms was created for a purely heuristic purpose. The entire purpose of the analysis is to decide what is computable. The method I choose accomplishes this goal. In other words -- if I use this algorithm for some input N, what is (roughly) the longest it might take to complete? This information is vital to see if a piece of code will meet performance specifications (for instance). If you have an O(n^5) algorithm, inputs of one billion and the specification says that the task must complete in one second, then you have a problem. That is what I use it for, and I think that is why we have some difference of opinion about how and why it ought to be done a certain way. You obviously use it for some other purpose. Perhaps another branch was formed in the annals of pure math, where we are seeking some other sort of thing.
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.