Total Amortized time complexity
But let’s be accurate for the worst time complexity without simplifying this time.
- If the internal array capacity starts with 1, then the capacities will be 1, 2, 4, 8, 16… X when it hits the capacity and gets doubled.
- It takes 1, 2, 4, 8 16 … X items to copy into the new array depending on the capacity that has been reached.
- So the time complexity will be 1 + 2 + 4 + 8 + 16 +… X. If you think from X, this will be X + X/2 + X/4 + X/8… + 1 = 2X approximately.
We try to show that even though some of the operations may be expensive, the sum (or, equivalently, the average) of their running times always has to be small.
We can understand it with the help of a diagram which contains an explanation about it with an example: