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
- boolean res = false; (line 6)
- 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!
>Solution :
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