Give an example of Algo/Program whose time complexity is O(log log n) ?

Question

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

Answer 1

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)