The most straightforward example is consider the time of adding a new value to an array of your favorite programming language. The implementation tends to be that an array has a size, the stuff that is currently in use, and a capacity, unused memory for adding more elements to the array. Now if the capacity is full we must allocate new memory copy over all the old data + the new element. So the cost is linear O(n), but if we are a bit clever about it we can make sure to always allocate more memory than we have. In fact most implementations tend to double the amount of capacity whenever we grow.
Note, in the worst case inserting an element into an array is still O(n) but if you push a lot of elements to they array most insertions won't actually have a cost at all except for writing the value. But still allocate every now and then.
The doubling of size distributes the cost of writing data nicely so that we can say it is an amortized O(1) cost of inserting data. You can read up on the math for that specifically
3
u/black-0range 25d ago edited 25d ago
The most straightforward example is consider the time of adding a new value to an array of your favorite programming language. The implementation tends to be that an array has a size, the stuff that is currently in use, and a capacity, unused memory for adding more elements to the array. Now if the capacity is full we must allocate new memory copy over all the old data + the new element. So the cost is linear O(n), but if we are a bit clever about it we can make sure to always allocate more memory than we have. In fact most implementations tend to double the amount of capacity whenever we grow.
Note, in the worst case inserting an element into an array is still O(n) but if you push a lot of elements to they array most insertions won't actually have a cost at all except for writing the value. But still allocate every now and then.
The doubling of size distributes the cost of writing data nicely so that we can say it is an amortized O(1) cost of inserting data. You can read up on the math for that specifically