# Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?

I have read in the book

"Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (Chapter 20)

that Emde Boas trees run min/max operations in $$\mathcal{O}(1)$$ time since the minimum and maximum element are stored as attributes in each tree. I don't understand this very well. Does this mean that the min and max values are already given in the input, because the minimum and maximum must be calculated somewhere?

## 2 Answers

No. They are not given as an input! They were stored and updated as an attribute of each tree(Beware that the concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure). The same situation is taking place in the min[Max]-heap data structure. You can find the minimum [maximum] in a min[max]-heap with $$O(1)$$ operation by keeping update (in insertion time) the mentioned attribute.

• I like to know in detail how these are saved and updated as attribute. It it just very vague for me when you say 'they are stored as a attribute'. How does it get updated when a node is inserted? What are the details? – NimaJan Jan 13 '20 at 15:57
• @NimaKimi The concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure. – OmG Jan 13 '20 at 20:07
• So when designing the data structure you will use a variable that automatically gets updated in some way to store the min/max? – NimaJan Jan 13 '20 at 22:03
• @NimaKimi Indeed nothing happens automatically. But it's keeping updated by checking that stored value is greater than the inserted value or not (depends on the min or max case). – OmG Jan 14 '20 at 12:37
• Thank for your answer. To summarize it, you can define an attribute by a variable that keeps track of the min/max in each operation you make on the tree. Is this it? – NimaJan Jan 14 '20 at 14:33

To search the min/max or successor/predecessor, we use a recursive algorithm that goes through the sub-trees and does the search. While the recursion happens, we don't calculate the min/max in every iteration. We have an attribute in an object that we get as an parameter to the recursive function that we use to assign the min/max. In every iteration, if there's a new min/max, then we assign the attribute to the new value so that we are always up-to-date with the min/max and when we need them, we can get them from the attribute which is $$O(1)$$.

recursiveFunction(metadataObj, x) {

if x < metadataObj.min:
metadataObj.min = x;

if x > metadata.max:
metadataObj.max = x;
}

• Very nice explanation! Thanks! I am glad you did a nice research. – NimaJan Jan 15 '20 at 17:07