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.

kindly have a look at my answer.

Deepak Tatyaji Ahire
– Deepak Tatyaji Ahire

2020-02-28 11:46:30 +00:00
Commented Feb 28, 2020 at 11:46 — Deepak Tatyaji Ahire
– Deepak Tatyaji Ahire, Commented Feb 28, 2020 at 11:46
cs.stackexchange.com/questions/71547/…

Sathvik
– Sathvik

2020-10-09 14:43:57 +00:00
Commented Oct 9, 2020 at 14:43 — Sathvik
– Sathvik, Commented Oct 9, 2020 at 14:43

Deepak Tatyaji Ahire · Accepted Answer · 2020-02-28 06:45:27Z

3

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)

edited Feb 28, 2020 at 6:45

answered Feb 28, 2020 at 6:40

Deepak Tatyaji Ahire

5,3915 gold badges21 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

complexity analysis of linear search in sorted array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related