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?
This is a late response but my solution is present on this Google Doc. Hopefully people in the future can benefit from my explanation:
Here is the link to the Google Doc I typed up: https://docs.google.com/document/d/16NrVWLNLi1Hxg8gCgkwZbCQ3zLciJOMmA4aU4tiCBDk/edit?usp=sharing
It is a little lengthy yes, but this is because I am explaining, most detailed as possible, the logic and the mathematics involved.
As a side note, readers may want to brush up on integration techniques, specifically partial fraction decomposition.
If there is anything that needs fixing, please comment on the Google Doc.
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.
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))
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.