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.
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.
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.
Fig. 03: Permutation Formula
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
3. Insertion Sort Time Complexity
4. Runtime Reduction of a Linear Search
5. Selection Sort Time Complexity