complexity analysis of linear search in sorted array

Question

Can anyone tell me that what will be the average time complexity of linear search when it is applied on a sorted array? I know worst case will be O(n) and best case will be O(1) but I dont know about average case in sorted array.

Answer 1

Let us suppose we have n elements in an array. Then as we know average case always work on probability theory i.e we assume that the probability of searching or finding an element at each location is same , then in this case as we have n elements so probability is 1/n...

Now, For successful search:

We might need to perform 1 comparison or 2 or 3 or 4 and so on ..

Therefore complexity(successful search) = 1(1/n) + 2(1/n) + 3(1/n) ..... n(1/n) = (n+1)/2

Also considering unsuccessful search:

complexity(unsuccessful search) = n (since we will look into all the array before considering it as unsuccessful).

Now, if q is the success probability , 1-q will be the probability of unsuccessful.

Therefore, Average complexity = q*(n+1)/2 + (1-q)*n

Here, q=1/2

Average complexity = (3n + 1/4) ~ O(n)