CODEWITHSUNDEEP
algorithmtime-complexity
Priyaranjan Swain
Priyaranjan Swain

Reputation: 361

Difference between constant time and effective constant time complexity

I understand "constant time complexity O(1)" , but when i came across the the term effective constant time complexity , i am very much confused . I got below sentence from Scala cook book about effective constant time .

The operation takes effectively constant time, but this might depend on some assumptions, such as maximum length of a vector, or distribution of hash keys.

But what i believe is above examples are not effective constant time , rather Amortize constant time .

Will you please give a clear difference between constant time and effective constant time . This will be very helpful .Thanks!!

Upvotes: 1

Views: 721

Answers (1)

Jörg W Mittag
Jörg W Mittag

Reputation: 369526

It means pretty much exactly what the quote says: it is not constant time, but, under some reasonable assumptions, it is only marginally worse than constant time, not enough to be noticeable.

So, it's not constant time, but it's so close that the difference doesn't matter, which effectively makes it (almost) constant time,

For example, implementing an array data structure as a 32-way tree technically makes it O(log n) instead of O(1). But an array with 4 billion entries will only be 6.4 levels deep, so it's basically less than 7 times slower than a traditional mutable contiguous array.

Upvotes: 3

Related Questions