Analysis of algorithm by Average-case

Question

I'm trying to solve a very simple algorithm analysis (apparently isn't so simple to me).

The algorithm is going like this:

int findIndexOfN(int A[], int n) {
// this algorithm looks for the value n in array with size of n.
// returns the index of n in case found, otherwise returns -1.
// it is possible that n doesn't appear in the array.
// n appears at most one time.
// the probability that n doesn't appear in the array is $1/(n+1)$
// for each cell in the array, the probability that n is found in index i
// is $1/(n+1)$


    int index, fIndex;
    index = 0;
    fIndex = -1;
    while (index < n && fIndex == -1) {
      if(A[index] == n) {
        fIndex = index;
      }
      index++;
    }
    return fIndex;

 }

Now I'm trying to calculate the average running time. I think this is Geometric series but I can't find out a way to merge between the terms probability and complexity.

For example, I know that in case the value n is found in index 1, then it would take 1 loop step to get the second index (1) and find n.

The probabilty on the other hand gives me some fractions....

Here is what I got so far:

$\sigma from i=1 to n evaluate ( (1/n) * ((n-1)/n)^i-1 )

But again, I can't find out the connection of this formula to T(n) and also I can't find a relation of BigOh, BigOmega or Theta for this function.

Answer 1

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 ith position (with probability 1/(n+1))

This series evaluates to

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