Author: Ricardo Gibert
Date: 11:08:10 05/09/01
Go up one level in this thread
On May 09, 2001 at 14:04:55, Eugene Nalimov wrote: >Uri, there is branch of the mathematics (not even computer science, just >ordinary mathematics) that studies the complexity of algorithms. Algorithms were >used in mathematics long before computers appeared, for example GCD algorithm >was known to the classic greeks. > >*Very* rude explanation of big-O notation is: you have the algorithm that >require M operations (or steps, or machine instructions, or clock cycles, etc.) >when input in N elements long. You are increasing length of the input; how much >operations will be necessary now? That has *nothing* to do with the fact that >majority of practically used algorithms will terminate in finite number of steps >when input is finite. > >Eugene But the the length of the input does not increase and that's the whole point. > >On May 09, 2001 at 13:37:58, Uri Blass wrote: > >>On May 09, 2001 at 13:23:25, Dann Corbit wrote: >> >>>On May 09, 2001 at 13:18:52, Uri Blass wrote: >>> >>>>On May 09, 2001 at 11:27:46, Dann Corbit wrote: >>>> >>>>>On May 09, 2001 at 10:12:30, Ricardo Gibert wrote: >>>>> >>>>>>On May 09, 2001 at 02:00:25, Dann Corbit wrote: >>>>>> >>>>>>>For those of you who don't want to perform your own web search, just choose one >>>>>>>of these: >>>>>>> >>>>>>>http://hissa.nist.gov/dads/HTML/bigOnotation.html >>>>>>>http://bio5495.wustl.edu/textbook-html/node15.html >>>>>>>http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html >>>>>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html >>>>>>>http://classes.monterey.edu/CST/CST338-01/world/BigO.html >>>>>>>http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O >>>>>>> >>>>>>>CS:201, FCOL! >>>>>> >>>>>>Big-O notation is used to describe asymtotic behavior. It commonly used to >>>>>>describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is >>>>>>understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets >>>>>>confused with infinity. This is an error, but let's not get into that. It isn't >>>>>>relevant here) >>>>>> >>>>>>In chess, n in is bounded. This is a critical distinction, that means chess is >>>>>>*not* NP. >>>>> >>>>>GREAT! Then it's computable. What's the answer, win-loss-draw? >>>>>;-) >>>> >>>>I see no point in continuing to argue. >>>>The question is simply question of definition. >>>>I did not say that it is easy to solve. >>>> >>>>I use the definition of NP only for problems with n that is not bounded >>>>otherwise the mathematical definition say that it is O(1)(there is a constant >>>>and the only problem is that it is too large) >>>> >>>>I can agree that chess is practically O(exp(n)) and not polynomial for practical >>>>purposes but it does not change the fact that by mathematical definition it is >>>>O(1). >>> >>>This is simply wrong. I guess we are at an impasse. >>> >>>>You can say that Sorting is also O(1) from theoretical point of view if you look >>>>at sorting that is done by a computer. >>> >>>Show me any algorithms book that says any sorting algorithm is O(1). >> >>The sorting from theoretical point of view is not O(1) because the size of the >>input is not bounded. >>Sorting done by a computer has bounded size and every problem of bounded size is >>O(1) by the definition that I know. >> >>A problem can be O(n) only if n is not bounded by a finite bound by the >>definition that I use. >> >>I look at sorting from mathematical point of view and not from computer point of >>view and this is the reason that I said that it is not O(1). >> >>Uri
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.