When at each level the size of data shrink by a factor of 2 then we get the complexity of o(Log n) but when the same shrink by the square root then we get the o(log log n).
Assume we have n data points where n = 256 then data will shrink in the following pattern i..e QuickSort etc
256/2 = 128
128/2 = 64
64/2 = 32
32/2 = 16
16/2 = 8
8/2 = 4
4/2 = 2
2/1 = 1
Total 8 steps
But if data is shrinking in the square root way then the pattern would be
256^.5 = 16
16^.5 = 4
4^.5 = 2
2^.1 = 1
Total 4 steps
Example of such algorithm
Van Emde Boas tree (Check http://en.wikipedia.org/wiki/Van_Emde_Boas_tree for more detail)
Space O(N)
Search O(log log N)
Insert O(log log N)
Delete O(log log N)