3 ms·
Linear time worst case and amortized constant time are not mutually exclusive. You are right that most containers that we use have amortized constant time compl
by jules 16y ago
Linear time worst case and amortized constant time are not mutually exclusive. You are right that most containers that we use have amortized constant time complexity, but they also have linear worst case complexity. Most times this is because an internal array has to be resized and the contents have to be copied over to the new enlarged array.
- jemfinch 16y agoNo, they're not mutually exclusive. But what actually matters in most software is "amortized constant time": linear time worst case only matters in hard real-time systems which can't tolerate any deviation from the expected runtime. Even algorithms like binary trees can end up with very bad worst cases unless great care is taken in allocating their nodes.