# Why is the number of comparisons in a BST missing key lookup about 2 ln N?

In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average. I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have 2 ln N compares?

• What part exactly are you having troubles understanding? – Yuval Filmus Mar 15 '17 at 12:54
• @YuvalFilmus edited the Q, I meant why it's (2 ln N) comparisons? – White159 Mar 15 '17 at 14:08
• You mention some explanation. Unfortunately I am not in a possession of the textbook, so I cannot read the explanation, and even if I could, I don't know which part of the explanation you don't understand. – Yuval Filmus Mar 15 '17 at 14:10
• Can you edit your question to include a self-contained summary of their explanation, and what parts you did understand, and what parts you didn't? You haven't given us much to work with. The more you give us to work with, the more likely someone can give you a helpful answer. If you didn't understand their explanation, I worry that if someone writes an explanation here you might just say that you didn't understand that, either. For instance, it'd be better to ask about some specific aspect you didn't understand. – D.W. Mar 15 '17 at 16:55

The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.

• I'm sorry. Just a few typos. 'ln' is shorthand for 'natural log', and 'lg' is shorthand for 'log'. My mistake using ln. And yes, I don't know how but the last sentence was truncated. It's been restored now. – E.D. Mar 15 '17 at 18:00
• OK. But now I'm confused about something different. If you really mean lg(n), there's a puzzling discrepancy -- your derivation proposes that the average number of comparisons should be 2 lg(n), but the question claims the right number is 2 ln(n), and asks for an explanation why the number is 2 ln(n). Put another way, your answer derives an answer of 2 lg(n), but the question quotes a book as claiming the answer is 1.39 lg(n). What gives? (lg always means the logarithm to base 2, ln always means logarithm to base e. If you are using them for something else, that is confusing.) – D.W. Mar 15 '17 at 19:59
• Also, why do you claim that the average height of a randomly generated binary search tree is lg(n)? What's your justification for that? That's the minimum height, but I would find it surprising if that's also the average height: the average should be higher than the minimum. Your derivation seems to have some gaps in it. – D.W. Mar 15 '17 at 20:02
• I'd been assuming the BST was balanced. A balanced BST has minimum height, so we know it's height is lg(n). You're right that ln and lg are different, and I did mean lg, but you should be aware lg often means log base 10. I did use lg meaning log base 2 in this case. I would disagree with the book, and say the number of comparisons is 2lg(n), not 2ln(n). I can't examine the book at the moment, so I might be wrong, but there's always a chance I'm wrong. – E.D. Mar 15 '17 at 20:14
• But that doesn't seem to be what the question is asking about. The question is asking about a random BST, i.e., where you insert one key at a time, and each key is chosen randomly. Such a BST will usually not have height exactly lg(n). (In my experience, in computer science lg(n) always means log to the base 2 -- never log to the base 10. Using it to mean base 10 would be crazy in CS -- anyone who uses that convention had darn well better define it explicitly in their writing.) – D.W. Mar 15 '17 at 20:24

You can say that O(2ln(n)) = O(ln(n))

It is easy to show that the search and misses are O(ln(n)).

Consider a binary search tree (BST). If you are searching from root, you either go left or right based on the knowledge of whether your search key is less than or greater than the value at root. So, when you select to go left (or right), you move one level down ignoring the nodes on the right (or left).

This way you will have to cover at most one node at any level. So, the number of nodes you cover in total is O(h) which is height of the tree.

Now, the height of the tree depends on the number of nodes according to:

O(h) = O(ln(n))

therefore, total number of nodes covered is O(h) = O(ln(n))

• I think the OP is rather interested in the constant 2, so ignoring the constant altogether won't do. – Yuval Filmus Mar 15 '17 at 15:43
• I do understand this, but I am asking why it's precisely (2 lg N), thanks! – White159 Mar 15 '17 at 16:41
• The height of a tree with n nodes can be up to n. Start with an empty tree, then insert the numbers 1 to n in ascending order. – gnasher729 Mar 16 '17 at 12:11

First, this seems weird, since 2 ln n is nowhere near 1.39 lg n. I'd say it is about 4.6 lg N.

You would need a very detailed analysis of the situation. If the binary tree was built by inserting the nodes in random order, a tree with 255 keys might have a height of 8 if you are extremely lucky, or a height of 255 if you are really unlucky, or anything in between. Then when you search for an item that is in the tree, it might be in the left branch or the right branch, and they will often have different heights, so the number of comparisons is limited by the height of the tree, but also limited by the height of each subtree that you enter.

So to find out why it is 2 ln N (IMPORTANT: There are several logarithms. log n or lg n or log10 n is usually base 10. ln N is usually base e. lb n or log2 n is base 2. In a comment you switched from 2 ln N to 2 lg N, which is something completely different), you have to follow and understand the analysis in that book. I could probably do that analysis for you, but if I had the time to do it, it wouldn't be any easier for you to understand than what two professional authors did.

• About the first sentence: check your reasoning. $2 \ln n$ is about $1.39 \lg n$. In particular, $2 \ln n = 2 \lg(n) \ln(2)$. Just to make sure we're on the same page: $\ln n$ is the log to the base $e=2.718...$; $\lg n$ is the log to the base $2$. – D.W. Mar 16 '17 at 15:24
• About the second paragraph: the question mentions on average, i.e., the expected value, taken over all possible outcomes. The average height of such a tree is indeed $O(\log n)$. (I don't know what the constant factor is.) I agree with your warnings about being careful about the base. One caveat: In computer science, we rarely use base 10, and $\lg n$ is essentially always log to the base 2 -- not log to the base 10. I would be amazed if this book used $\lg n$ to mean log to the base 10. – D.W. Mar 16 '17 at 15:28
• Many times in CS problems, it doesn't matter whether you mean log2 or log10. For example, O (log n) = O (log2 n) = O (log10 n) = O (ln n). When it matters, like here, I would really recommend to use log2 or log10 including the base to avoid any confusion. Yes, I took lg n to mean log10. – gnasher729 Mar 16 '17 at 18:20
• And just saying: Fascinating that a problem with a best case log2 (n) turns out to have an average case of 2 x ln (n). And interesting that it is so little. Half the time the larger side of the tree will contain 3/4 or more of the keys, which means it's height isn't reduced much, and the majority of the keys is on that side. – gnasher729 Mar 16 '17 at 18:26