Best and Worst-Case Analysis of Linear Search and Binary Search Tree

Are you new to algorithm studies and looking for examples to learn about linear and binary search tree analysis? Then this post is for you.

Linear search is one of the simplest searches out there. In linear search, elements are searched one by one. Usually, the element is searched and named as the key, and you are asked to find a matching key in a list or array.

Let's say our key element is 2, we will start scanning the list from the left-hand side for a linear search. We will check each element at a time. This search will continue until it finds the key.

key=2   
                   *
      [3,4,5,12,14,2,7,15,18,19]
idx =  0 1 2  3  4 5 6  7  8  9

The key is found after iterating through all elements till index 5.

Let's say you are asked to search for the key =21.

key = 21   
      [3,4,5,12,14,2,7,15,18,19]
idx =  0 1 2  3  4 5 6  7  8  9

In the above example, we will search from the first index and traverse the entire array to confirm that 21 is not present in the array.

The best case for a linear search happens when we search for a key present at the first index, with a constant time O(1). The worst-case would be searching for a key at the last index, with O(n) complexity.

Your data structure doesn't have to be an array to search an element; it could be, for instance, a tree. Let's look at a Binary Search tree, for example:

Binary Search Tree(BST) examples by Hatice Karatay

All trees you see at the top are valid binary search trees. The best case to find an element in a tree would be finding it at the root of a tree with O(1) complexity. The worst case of finding a value at a leaf node for the balanced tree is O(log n)/the height of the tree. For the left/right skewed tree, to reach a leaf node, all nodes need to be visited, which would give us O(n) worst-case complexity.