And here's another interesting algorithm/structure: Randomized Slide to Front

[Ola Fosheim Grøstad via Digitalmars-d]

On Tuesday, 1 December 2015 at 01:12:39 UTC, Chris Wright wrote:
> People typically use lax terminology. Here, when someone 
> doesn't specify whether they're talking about average or worst 
> case complexity for an algorithm, they're probably talking 
> about average case.

Don't use lax terminology when doing complexity analysis. Average 
case analysis is much much much harder to do than worst 
case/amortized.