top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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 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
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...