What is meant by "Constant Amortized Time" when talking about
time complexity of an algorithm? Amortised time explained in
simple terms: If you do an operation say a million times, you
don't really care about the worst-case or the best-case of that
operation - what you care about is how much time is taken in
total when you repeat the operation a million times. So it
doesn't matter if the operation is very slow once in a while, as
long as "once in a while" is rare enough for the slowness to be
diluted away. Essentially amortised time means "average time
taken per operation, if you do many operations". Amortised time
doesn't have to be constant; you can have linear and logarithmic
amortised time or whatever else. Let's take mats' example of a
dynamic array, to which you repeatedly add new items. Normally
adding an item takes constant time (that is, So each time you
enlarge, you take about twice as much time as the last enlarge.
But you've also waited twice as long before doing it! The cost
of each enlargement c