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