# Minimum finger search tree complexity

Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $$k$$-smallest key in the entire tree. I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as

(x > curr.key) && (x > curr.parent.key)

I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.

The claim is that the worst case complexity is always $$O(\log k)$$, for any $$k$$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $$k > {n\over 2}$$), that implies I must have traversed the entire left branch, which for a balanced tree is $$O(\log n)$$ - and only then I can find x in depth of $$O(\log k)$$.

Am I looking at this the wrong way?

• "The claim is that ...". Can you add a url or reference to the place of that claim? – Apass.Jack Dec 6 '18 at 19:44
• It looks like you have understood the whole situation correctly except a minor glitch somewhere. By the way, if $n\ge k>n/2$, then $O(\log n)$ is $O(\log k)$ – Apass.Jack Dec 6 '18 at 19:47
• @Apass.Jack The claim was from my class... and no further information on that topic is provided, either. I understand your note, but still - climbing up the tree isn't done in a constant time, the height from the minimum is still $O (\log n)$. The technicality for bigger k's doesn't hold, it seems. So you're saying there's no way to achieve $O(\log n)$ without comparing with the root first? – gbi1977 Dec 6 '18 at 20:57

Yes, you might be looking it the wrong way.

If $$x$$ is larger than the tree's root's key (the median, or equivalently $$k>n/2$$), that implies I must have traversed the entire left branch, which for a balanced tree is $$O(\log n)$$ - and only then I can find $$x$$ in depth of $$O(\log k)$$.

First, let us be accurate. The root's key may not be the median, although it sits roughly in the middle.

Let $$r$$ be the root node. Let $$n$$ be the number of nodes in the whole tree and $$n_l$$ be the number of nodes in the left subtree of $$r$$. Let $$h_l$$ be the height of that subtree and $$h$$ be the height of the tree, so $$h\le h_l+2$$ since an AVL tree is height balanced.

Suppose $$x$$ is larger than the root's key. That means $$n_l < k \le n.$$ We also have, according to the properties of an AVL tree. $$\log_2 (n+1)\le h \le h_l+2 \le c\log_2(n_l+2)+b +2\lt c\log_2(k+2)+b +2$$ where $$c\approx 1.44$$, $$b\approx -0.328$$. So, for all $$k\ge3$$, $$\log_2(n)\le2\log_2(k)$$

So if you have traversed the entire (height) of the left branch in order find the $$k$$-th smallest element, you will use $$O(\log n) = O(\log k)$$ steps.

In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $$k$$-th smallest element, we have just proved that the worst case complexity is always $$O(\log k)$$