C++ High Performance

Amortized time complexity

Usually, an algorithm behaves differently with different inputs. Going back to our algorithm that linearly searched an element in an array, we were analyzing the case where the key was not in the array at all. For that algorithm, that was the worst case—that is, it used the most resources the algorithm will need. The best case refers to the least amount of resources the algorithm will need, whereas the average case states how many resources the algorithm will use on average with different input.

The STL usually refers to the amortized running time of functions that operate on containers. If an algorithm runs in constant amortized time, it means that it will run in O(1) in almost all cases, except a very few where ...