Binary Search Tree Time Complexity

Introduction to Binary Search Tree

In this post, we are going to discuss one of the important search algorithm's time complexity which binary search tree. This algorithm enables to search for and to find an element in an array of a tree using the average running time which is a logarithmic multiplier. To find the time complexity of such an algorithm, as usual like others post of time complexity we will draw an example to understand the topic adequately.

Time Complexity of Binary Search Tree

Assume we're looking for a piece of information (can be an item) in a binary search tree T (Consider the below binary tree). Take note that the number of comparisons between items is limited by the depth size of the binary tree. This is because we are moving from root to the child using a single path of tree T. As a result, the running time duration of the binary search will be proportional to the depth of the tree T. 

Binary Search Tree

Fig. 01: The Binary Search Tree T

I think we are not clear about the time complexity of the binary search tree from the above information. Then, again assume we have n data items with n-length size for the processing of the data and the items are a1, a2, a3 ........ an, and they are placed in the correct sequence into a binary search tree T. For better understanding, we depict a figure below. 

Binary Search Tree with n data items

Fig. 02: Binary Search Tree with n data items.


If you have a clear idea about the permutation process then we can say that the n items might be permuted in n! ways. 

permutation formula

Fig. 03: Permutation Formula

permutation process

Fig. 04: Permutation Process of n items


Each such permutation will result in the expansion of a tree in a sequence. The average depth of the n! trees may be calculated to be around log2 n. As a result, the average running time bst(n) i.e. binary search tree(n) to find an item in a binary tree T with the following n entries is proportional to log2 n, then we can write about the time complexity of the binary search tree is, 

Time Complexity = Depth of the tree

= n-lenght data processing

= bst(n)

= permutation of n in n! ways

log2n

Using the Big O notation the time complexity of the binary search tree is O(log2n).

Read Similar Post

1. Merge Sort Time Complexity

2. Quick Sort Time Complexity

3. Insertion Sort Time Complexity

4. Runtime Reduction of a Linear Search

5. Selection Sort Time Complexity

6. Bubble Sort Time Complexity

7. Heap Sort Time Complexity

Post a Comment

Previous Post Next Post