Complexity nomenclature

tn via Digitalmars-d digitalmars-d at puremagic.com
Fri Dec 4 06:45:19 PST 2015


On Friday, 4 December 2015 at 14:08:08 UTC, Andrei Alexandrescu 
wrote:
> On 12/04/2015 04:51 AM, tn wrote:
>> "I just want to insert an element. I don't care how long it 
>> takes. Why
>> do I need to specify that it should be linear?"
>
> Oh but you do care.

I don't, if I have a small container of constant size (or bounded 
by a small constant). Say, less than 10 elements.

Or perhaps I just want to quickly make some prototype.

And if the other part of my algorithm is exponential or even 
superexponential, then it is going to dominate anyway. Or should 
there be also baseTwoExponentialInsert etc. for the case in which 
I don't care as long as the complexity is at most O(2^n)?

>> In my opinion, there should be "constantInsert", 
>> "linearInsert", etc.
>> for those who care about the complexity, and "insert" should 
>> be always
>> available.
>
> What would be the complexity assumption of "insert"?

None. So in a sense that would be an alias of whateverInsert or 
idontcareInsert or infinityInsert.



More information about the Digitalmars-d mailing list