Hello, in the image you see a very simple algorithm of a contains function, which should just switch from boolean false to boolean true, if c is in the array[] a.

Now i want to calculate the average case of this algorithm. Best case and worst case are easy to look through, but i am quite unsure how to get to the average one.

The array[] a hat n elements and c should be at index i.

So far, i know: T avg(n) = sum[p(x) * T(x)], where p(x) stands for the probability, to get input x.

*First of all i have to count the elementary operations, to find c. *

Tbh, i struggle there and can't get behind it. As far as i know, from colleagues and my prof, the amount of elementary operations to find c is: T n,j = 2 + 3(j + 1).

It would be much appreciated, if anyone could be explain to me why it's 2 + 3(j + 1).

My guess is that 2 comes from

1. boolean res = false; (line 6)
2. int i = 0; (line 7)

If that's correct (what i don't consider it to be) where does the 3 come from? I don't have to go through the array 3 times, because n is 4 (or do i?).

Any help is much appreciated, because i really can't get behind that 2 + 3(j + 1). Thank you!

T avg(n) = sum[p(x) * T(x)]

= 1/n + 2/n +...+ (n-1)/n + n

= 1/n (1+2+...n)

= n(n+1)/2n = (n+1) / 2