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

Answer 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.