Author: Andrew Dados
Date: 12:18:12 05/09/01
Go up one level in this thread
On May 09, 2001 at 15:11:41, Eugene Nalimov wrote: >Ok, here is simple example: let's consider sorting but limit the input by (a) >limiting # of digits in each number (e.g. 1024 bits), and (b) limiting # of >elements in the sequence we want to sort (e.g. max 10**40 elements). Yes, >theoretical # of operations that are necessary to sort such a sequence is >limited. But, nevertheless, you still can say that >* insertion sort is O(N*N), >* quick sort is O(N*ln(N)) on average, but O(N*N) in the worst case, >* heap sort is O(N*ln(N)) in the worst case. >So I don't see why the fact that something is finite changes something in the >complexity tree search. > >Eugene Wrong example. Instead consider sorting a set (2,42,15,103,37). Sort it; save a solution. Then what is a cost of sorting exact same set again? There is infinite sets of numbers to sort; there is only one chess position to solve.... -Andrew-
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.