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

[Chris Wright via Digitalmars-d]

On Mon, 30 Nov 2015 23:27:24 +0000, Ola Fosheim Grøstad wrote:

> 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.

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. Similarly for 
amortized algorithms. Andrei is no doubt aware of the worst case (which 
in this case is O(inf), not O(N)) and has responded to people talking 
about ways to reduce the worst case.

This doesn't mean Andrei was wrong or misspoke; it means that he could 
have been marginally clearer. Most people instantly grok the intent, but 
some who are blessed with pedantry don't.

Identifying these cases is a skill that took me years to learn.