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

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu 
wrote:
> So let's improve on that: whenever an element is found in 
> position k, pick a random number i in the range 0, 1, 2, ..., k 
> inclusive. Then swap the array elements at indexes i and k. 
> This is the Randomized Slide to Front strategy.
>
> With RStF, worst case search time remains O(n), as is the 
> unsuccessful search. However, frequently searched elements 
> migrate quickly to the front - it only takes O(log n) searches 
> to bring a given value at the front of the array.

Something is wrong with the math here.  The randomization means 
that you must assume that you get element k-1 in the worst case, 
so if you repeatedly search for the same element you need O(N) 
repeats to move it to the front, so you get O(N^2) complexity for 
moving any element to the front.

Right?

You are probably thinking about the average case analysis, which 
is a more sensible theoretical concept for randomized algorithms 
than worst case, but then you need a model for what is typical.