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

+1 vote
92 views

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) posted Jun 24, 2014
Share this question

## 1 Answer

0 votes

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)
`````` answer Jun 24, 2014 by anonymous
Similar Questions
+3 votes

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.