Question

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.

Answer 1

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