top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+1 vote
395 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 by Sachidananda Sahu

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

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
...