4 ms·
An important thing to know: amortized analysis. (Most of you will already know this, of course.) This is especially useful for operations that happen often.
by stcredzero 17y ago
An important thing to know: amortized analysis. (Most of you will already know this, of course.) This is especially useful for operations that happen often. This is how we know that an array that grows by doubling its storage when needed has O(1) for adding to the end.
Hint:
O
XX
OOOO
XXXXXXXX
OOOOOOOOOOOOOOOO
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
...
You can always arrange all but the biggest array alongside the biggest array, with one space left over. So you can always amortize the cost of an array copy over the number of add operations that preceded it.
OOOOOOOOOOOOOOOOXXXXXXXXOOOOXXO
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX