Finding the Average case complexity of an Algorithm

Question

I have an algorithm for Sequential search of an unsorted array:

SequentialSearch(A[0..n-1],K)

i=0
while i < n and A[i] != K do
    i = i+1
if i < n then return i
else return -1

Where we have an input array A[0...n-1] and a search key K

I know that the worst case is n, because we would have to search the entire array, hence n items O(n)

I know that the best case is 1, since that would mean the first item we search is the one we want, or the array has all the same items, either way it's O(1)

But I have no idea on how to calculate the average case. The answer my textbook gives is:

= (p/n)[1+2+...+i+...+n] + n(1-p)

is there a general formula I can follow for when I see an algorithm like this one, to calculate it?

PICTURE BELOW Textbook example

EDIT: Check the picture I've added which shows the solution, I just don't know how they're getting it. — o4o42o3k2o
– o4o42o3k2o, Commented Feb 17, 2017 at 1:37
@mitch wheat, exactly. My answer below is consistent with the entry you've linked to. Apparently someone impulsively down-voted it because it went over their head. — Adrian M.
– Adrian M., Commented Feb 17, 2017 at 1:41

夢のの夢 · Accepted Answer · 2017-02-17 02:40:15Z

3

= (p/n)[1+2+...+i+...+n] + n(1-p)

p here is the probability of an search key found in the array, since we have n elements, we have p/n as the probability of finding the key at the particular index within n . We essentially doing weighted average as in each iteration, we weigh in 1 comparison, 2 comparison, and until n comparison. Because we have to take all inputs into account, the second part n(1-p) tells us the probability of input that doesn't exist in the array 1-p. and it takes n as we search through the entire array.

answered Feb 17, 2017 at 2:40

夢のの夢

6,01811 gold badges43 silver badges72 bronze badges

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

Comments

Adrian M. · Accepted Answer · 2017-02-17 01:48:03Z

1

You'd need to consider the input cases, something like equivalence classes of input, which depends on the context of the algorithm. If none of those things are known, then assuming that the input is an array of random integers, the average case would probably be O(n). This is because, roughly, you have no way of proving to a useful extent how often your query will be found in an array of N integer values in the range of ~-32k to ~32k.

edited Feb 17, 2017 at 1:48

answered Feb 17, 2017 at 1:34

Adrian M.

3518 silver badges17 bronze badges

3 Comments

o4o42o3k2o Over a year ago

I've added a picture, it can't be O(n), I guess I'm just not sure about the process of getting the average case.

o4o42o3k2o Over a year ago

Right, but how does the textbook get that answer? I don't understand all those sums where do they come from? If and when I get tested on something like this, I'll need to be able to reproduce whatever the hell they're doing there.. and well I don't know how.

Adrian M. Over a year ago

It's confusing notation for sure. I would take a look at other sources to understand how probability is involved, and then try to parse the text notation.

Sandipan Dey · Accepted Answer · 2017-02-17 10:21:01Z

More formally, let X be a discrete random variable denoting the number of elements of the array A that are needed to be scanned. There are n elements and since all positions are equally likely for inputs generated randomly, X ~ Uniform(1,n) where X = 1,..,n, given that search key is found in the array (with probability p), otherwise all the elements need to be scanned, with X=n (with probability 1-p).

Hence, P(X=x)=(1/n).p.I{x<n}+((1/n).p+(1-p)).I{x=n} for x = 1,..,n, where I{x=n} is the indicator function and will have value 1 iff x=n otherwise 0.

Average time complexity of the algorithm is the expected time taken to execute the algorithm when the input is an arbitrary sequence. By definition,

The following figure shows how time taken for searching the array changes with n and p.

Collectives™ on Stack Overflow

Finding the Average case complexity of an Algorithm

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related