Sunday 29 April 2012

An experiment in Van Emde Boas layouts

Given an arbitrarily large sorted, balanced binary tree of values, the obvious way to search for elements is binary search. In undergraduate classes I learned that a binary search requires log(n) operations and is thus as efficient as you can get without throwing additional storage space at the problem. One thing my lecturer didn't dive into though was the effect of CPU cache on this otherwise simple little log(n) algorithm.