What is the time complexity for storing the maximum number of elements in Van Emde Boas tree if M is the maximum number of elements?

Category: QuestionsWhat is the time complexity for storing the maximum number of elements in Van Emde Boas tree if M is the maximum number of elements?
Editor">Editor Staff asked 4 weeks ago

What is the time complexity for storing the maximum number of elements in Van Emde Boas tree if M is the maximum number of elements?
 
(a) O (log M)
 
(b) O (M!)
 
(c) O (M)
 
(d) O (1)
 
This interesting question is from Trees topic in division Trees of Data Structures & Algorithms I
 
The question was posed to me during an internship interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct option is (c) O (M)
 
The best I can explain: In order to store the maximum number of elements in Van Emde Boas data structure where M is the maximum number of elements, the tree has great efficiency for storing them. So the time complexity for worst case is found to be O (M).