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

data-structures time-complexity big-o binary-search-tree
Hommer Smith picture Hommer Smith · Jan 20, 2013 · Viewed 46.2k times · Source

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

Mike Higginbottom picture Mike Higginbottom · Jan 20, 2013

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).

Related questions

Hash table runtime complexity (insert, search and delete)

Why do I keep seeing different runtime complexities for these functions on a hash table? On wiki, search and delete are O(n) (I thought the point of hash tables was to have constant lookup so what's the point if …

Read More
What are the time complexities of various data structures?

I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, but I guess some of us are …

Read More
Explanation of runtimes of BFS and DFS

Why are the running times of BFS and DFS O(V+E), especially when there is a node that has a directed edge to a node that can be reached from the vertex, like in this example in the following …

Read More