Author: Eugene Nalimov
Date: 11:04:55 05/09/01
Go up one level in this thread
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 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.