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.

alestanis · Accepted Answer · 2012-11-02 19:09:29Z

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

edited Nov 2, 2012 at 19:09

answered Nov 2, 2012 at 19:01

alestanis

22k4 gold badges50 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

SyndicatorBBB Over a year ago

I need the average running time mostly. I want to know how to do this although I agree withyou that it's sounds like n. I saw in class some examples of average cases runing time becoming logn. I just want to understand the right way to do it formaly.

SyndicatorBBB Over a year ago

First of all, this is very nice observation. I just need some formal explanation on this.

SyndicatorBBB Over a year ago

Just one more thing. What about the chance n doesn't appear? you ignored it right? I mean, there is a purpose for this information or I can ignore it?

alestanis Over a year ago

Yes, I forgot about it. That would add n/(n+1) to the series, which would have been ignored anyway.

SyndicatorBBB Over a year ago

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

|

Collectives™ on Stack Overflow

Analysis of algorithm by Average-case

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related