CODEWITHSUNDEEP
arraysalgorithmtime-complexitycomplexity-theoryasymptotic-complexity
o4o42o3k2o
o4o42o3k2o

Reputation: 13

Finding the Average case complexity of an Algorithm

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

Upvotes: 1

Views: 1651

Answers (3)

Sandipan Dey
Sandipan Dey

Reputation: 23101

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,

enter image description here

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

enter image description here

Upvotes: 0

夢のの夢
夢のの夢

Reputation: 5826

= (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.

Upvotes: 3

Adrian M.
Adrian M.

Reputation: 352

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.

Upvotes: 1

Related Questions