Author: Uri Blass
Date: 15:32:59 05/09/01
Go up one level in this thread
On May 09, 2001 at 18:13:15, Dann Corbit wrote: <snipped> >>You can look at sorting(not from computer's point of view) as an infinite number >>of problems(sorting 1 element,sorting 2 elements....) when everyone of them can >>be solved in a finite time but the input is not bounded. >> >>You have no constant C such that every one of the problems can be solved in less >>than C units of time. >Not only is that not correct, but I detailed examples. For instance, in the >ANSI C99 language, the highest precision counting type that can be relied upon >is unsigned long long. Hence, the maximum possible time to sort a vector via >comparison is O(n*(log((2^64-1)!)) which is a constant. I explained that I talk about sorting not from a computer's point of view. I talk about sorting from the point of view of a non existing machine when the number of elements is not bounded and the precision is not bounded. Another point is that O(n*log(2^64-1)!)=O(n). It is clear that from practical point of view it is worse than O(n) because the constant is too big but from computer's point of view you can look it also as O(1) because n is bounded by the memory of the computer when the only problem is that the constant that you get is too big. I am not going to continue to argue about it. I am using a definition that I studied at university. I can agree that the fact that searching n plies is O(1) by the defintion is not important for practical purposes. 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.