# Lookup complexity in augmented interval tree

If we consider the following problem: Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point, and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.

• Are you interested in the amortized complexity? Did they tell you if they want the total cost, was it clear whether the cost of building the data structure had to be included? In either case, the answer to the question your posing is in the link you have included. I am guessing there was some space limitation you forgot to add or some other extra parameter? Commented Jul 9, 2015 at 20:50
• No, that link doesn't give the lookup complexity for ALL intervals intersecting a given point for the augmented version of the interval tree. Commented Jul 10, 2015 at 2:53

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$. Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

Illustrated example:
Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$). All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored. However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time. Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time. Because we prune a tree-walk we also have an upper bound of $O(n)$ time. This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.

• But if m=n, then this will give a lookup complexity of O(n log n), which cannot be the case since tree traversal is O(n) Commented Jul 15, 2015 at 19:24
• Could you elaborate on the answer you have posted? Specifically, the part related to "at most one downward path.." and how that translates to O(min(n,(m+1)logn))? Commented Jul 15, 2015 at 22:46
• @user1715122: I updated my answer.
– Tim
Commented Jul 17, 2015 at 6:33