Analysis Of Algorithms University of Bridgeport Analysis of Algorithms

First we need to set up a model.

As a first step we’ll determine the average case complexity given that the element is present in the array. Here, we take into account the probability of not finding an element at a particular level (in worst case we assumed had taken this part to be one i.e. the element being not found at a particular level was taken as a certainty) and add to it the work done at the next level recursively.

Thus,

Repeating ‘i’ times,

Let ‘i = k-1’,