Complexity nomenclature

ZombineDev via Digitalmars-d digitalmars-d at puremagic.com
Fri Dec 4 01:33:42 PST 2015


On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad 
wrote:
> On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
>> and space complexity (the correctness is given). Otherwise, 
>> designing large systems becomes impossible, because all large 
>> systems have hard performance requirements.
>
> I am sorry to say this, but hard performance requirements 
> require O(1) on everything.
>
> Big-Oh tells you essentially very little if it is more than 
> O(1). Quick sort and insertion sort are O(N^2), bucket sort is 
> O(N). That does not make bucket sort faster than quick sort or 
> even insertion sort on a specific case as it is dominated by 
> the number of possible values.

Well, I agree, but I didn't say hard real-time, only performance 
requirements that are hard to achieve because the system is 
large, and becuase it would cost even more if the system was 
larger (slower).


More information about the Digitalmars-d mailing list