This algorithm is BigOh(n), BigOmega(n) and Theta(n).
To know this you don't need to compute probabilities or use the Master Theorem (as your function isn't recursive). You just need to see that the function is like a loop over n
terms. Maybe it would be easier if you represented your function like this:
for (int i = 0; i < n; ++i) {
if (A[i] == n)
return i;
}
I know this seems counterintuitive, because if n
is the first element of your array, indeed you only need one operation to find it. What is important here is the general case, where n
is somewhere in the middle of your array.
Let's put it like this: given the probabilities you wrote, there is 50% chances that n
is between the elements n/4
and 3n/4
of your array. In this case, you need between n/4
and 3n/4
tests to find your element, which evaluates to O(n)
(you drop the constant when you do BogOh analysis).
If you want to know the average number of operations you will need, you can compute a series, like you wrote in the question. The actual series giving you the average number of operations is
1/(n+1) + 2/(n+1) + 3/(n+1) ... + n/(n+1)
Why? Because you need one test if n
is in the first position (with probability 1/(n+1)
), two tests if n
is in the second position (with probability 1/(n+1)
), ... i
tests if n
is in the i
th position (with probability 1/(n+1)
)
This series evaluates to
n(n+1)/2 * 1/(n+1) = n/2