w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Amortized analysis

Expected time:

We make some assumptions and, based on these assumptions, we make statements about the running time.

Hash tables is one such example. We assume that the data is well-distributed, and claim that the running time of operations are O(1), whereas the worst-case running time for an operation is actually O(n).

Amortized time:

Even though one operation may take longer than some given time, the time across multiple operations will balance out to give the mentioned running time.

(Well-implemented) self-resizing arrays is one such example. When you insert, it takes O(n) to resize the array, but, across many inserts, each will take O(1) on average.

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.