[estebarb]

There are tricks: if you need to find uniformly distributed data it is unbeatable: guaranteed to work in 5 hops or less. After 5 hops, is better to use binary search. If data is not uniformly distributed one trick is to sort by hash of the element (store the hash with the element or calculate on the fly). But yeah, without those adjustments it has a worst case of O(n).