Does Van Emde Boas data structure perform all operation in O (log (log M)) time where M = 2^m.

Category: QuestionsDoes Van Emde Boas data structure perform all operation in O (log (log M)) time where M = 2^m.
Editor">Editor Staff asked 4 weeks ago

Does Van Emde Boas data structure perform all operation in O (log (log M)) time where M = 2^m.
 
(a) True
 
(b) False
 
My question is based upon Trees in division Trees of Data Structures & Algorithms I
 
The question was posed to me in an international level competition.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (a) True
 
Best explanation: All the operations performed on the Van Emde Boas tree with an associative array like Insertion, Deletion, Searching and many more can be performed in O (log (log M)) time where M = 2^m.