Why lookup in a Binary Search Tree is O(log(n))?

Question

I can see how, when looking up a value in a BST we leave half the tree everytime we compare a node with the value we are looking for.

However I fail to see why the time complexity is O(log(n)). So, my question is:

If we have a tree of N elements, why the time complexity of looking up the tree and check if a particular value exists is O(log(n)), how do we get that?

Answer 1

Your question seems to be well answered here but to summarise in relation to your specific question it might be better to think of it in reverse; "what happens to the BST solution time as the number of nodes goes up"?

Essentially, in a BST every time you double the number of nodes you only increase the number of steps to solution by one. To extend this, four times the nodes gives two extra steps. Eight times the nodes gives three extra steps. Sixteen times the nodes gives four extra steps. And so on.

The base 2 log of the first number in these pairs is the second number in these pairs. It's base 2 log because this is a binary search (you halve the problem space each step).

Answer 2

For me the easiest way was to look at a graph of log2(n), where n is the number of nodes in the binary tree. As a table this looks like:

          log2(n) = d

          log2(1) = 0
          log2(2) = 1 
          log2(4) = 2
          log2(8) = 3
          log2(16)= 4 
          log2(32)= 5
          log2(64)= 6             

and then I draw a little binary tree, this one goes from depth d=0 to d=3:

            d=0          O
                        / \
            d=1        R   B
                      /\   /\
            d=2      R  B R  B
                    /\ /\ /\ /\
            d=3    R B RB RB R B

So as the number of nodes, n, in the tree effectively doubles (e.g. n increases by 8 as it goes from 7 to 15 (which is almost a doubling) when the depth d goes from d=2 to d=3, increasing by 1.) So the additional amount of processing required (or time required) increases by only 1 additional computation (or iteration), because the amount of processing is related to d.

We can see that we go down only 1 additional level of depth d, from d=2 to d=3, to find the node we want out of all the nodes n, after doubling the number of nodes. This is true because we've now searched the whole tree, well, the half of it that we needed to search to find the node we wanted.

We can write this as d = log2(n), where d tells us how much computation (how many iterations) we need to do (on average) to reach any node in the tree, when there are n nodes in the tree.