O(lg lg N) is a smaller growth rate than O(lg N).

Of course, for smaller datasets it doesn't matter.

In fact if you do sorting, for small datasets (that are mostly sorted) a bubble-sort is better than quick-sort, since it doesn't involve random disk accesses and it might even require fewer steps.

I would be curious if this method for searching would apply to sorting (e.g. sorting done in O(N lg lg N)) ... since I remember that sorting done with comparisons can't be better than O(N lg N) (the height of a binary search tree is lg N ... and I think the demonstration was based on that).

So to get back on-topic ... it really depends on the size of your data.