what is amortized time complexity?? Please simplify this
Amortized time complexity
Amortized complexity is the total expense per operation, evaluated over a sequence of operations.
Example:
The behavior of C++ std::vector<>
. When push_back()
increases the vector size above its pre-allocated value, it doubles the allocated length.
So a single push_back()
may take O(N)
time to execute (as the contents of the array are copied to the new memory allocation).
However, because the size of the allocation was doubled, the next N-1
calls to push_back()
will each take O(1)
time to execute. So, the total of N
operations will still take O(N)
time; thereby giving push_back()
an amortized cost of O(1)
per operation.