When studying the performance of data structures, we look at three key things:

• Correctness: The data structure should correctly implement its interface.
• Time Complexity: The running times of operations on the data structure should be as small as possible
• Space Complexity: The data structure should use as little space as possible.

Here, we can take correctness as a given; we won't study any data structures that give incorrect answers to queries or don't perform updates properly. However, we will study data structures that endeavor to minimise space usage. This generally won't affect the (asymptotic) running times of operations, but can realistically make data structures a little slower.

During the study of running times in the context of data structures we mostly find three different kinds of running time guarantees:

• Amortized running times:
If we state the amortized running time of an operation in a data structure is f(n), then this translates as the cost of a typical operation being at most f(n). To be more accurate, if a data structure has an amortized running time of f(n), then a sequence of m operations takes at most mf(n) time. Some individual operations may take more time than f(n) but the average, across the full sequence of operations, is at most f(n).
• Expected running times:
If we state that the expected running time of an operation in a data structure is f(n), then this translates as the actual running time being a random variable and the expected value of this random variable is at most f(n). The randomisation here is relating to random choices made by the data structure.
• Worst-case running times:
Arguably the most predominant of running time guarantees. If a data structure operation has a worst-case running time of f(n), then one of these operations never takes longer than f(n) time.

To understand the differences between running times we can consider a metaphorical example regarding long-term loans:

Presume one desires to make a large purchase of £100,000 (small house, luxury boat, food in britain's current economy). In order to make this purchase we might take out a 10 year loan (120 months) with monthly payments of £1200. In this example, the worst-case monthly cost of the loan is £1200.

However, if we were lucky enough to have £100,000 in the bank, we might choose to make the purchase outright. In this case, over the same 10 year period the amortized cost would be £100,000/120 months = £833.33_r which is much less (366.67 pcm) than the loan.

No we have made our large, (most likely) extravagent purchase we naturally want protect it from damage and theft. By studying hundreds of thousands of cases, insurance companies have determined that the expected amount to replace our item is £10 a month. The number is small because houses and luxury boats are rarely stolen and suffer damage infrequently (but do so occasionally). Upon contacting not-a-scam insurance company we are given the quote of £15 per month to insure our item from theft and damages.

Now we have a decision to make. Do we pay the £15 worst-case monthly cost, or should we take the risk and self-insure at an expected cost of £10 a month? Obviously, the £10 per month costs less in expectation, but we have to accept the possibilty that the actual cost may be much higher. In the unlikely event our new house/boat is stolen (or destroyed completely), the actual cost would be £100,000.

These examples are supposed to offer an insight into why we sometimes settle for amortized or expected running times over worst-case. It is often conceivable to achieve a lower expected or amortized running time than a worst-case. To put it mildly, it is very often possible to achieve a much simpler data structure if we abide by amortized or expected running times.