Thread: Is this the correct big O average case complexity for this algorithm?

Code:

unsigned rnd(unsigned limit)
{
    return rand() % limit;           // O(1)
}
 
void permute (int a[], int n)
{
    bool* used = new bool[n];        // O(1)
    fill (used, used+n, false);      // O(used+n)
    for (int i = 0; i < n; i++)      // O(1)  n*  = O(n)
    {
        a[i] = rnd(n);               // O(1)
        while (used[a[i]])           // O(1)  n* = O(n)
        {
            a[i] = rnd(n);           // O(1)
        }
        used[a[i]] = true;           // O(1)
    }  
    delete [] used;                  // O(1)
}

So it would be O(used+n^3)?

The for loop and while loop both run in linear time (O(n)) and since they are nested you would get quadratic complexity (O(n^2)). The fill operation is not in any loop however so i don't know why you end up with O(n^3), it should be O(n + n^2)....however:

Coefficients and constant factors are usually omitted from complexity analysis since they are practically irrelevant for large values of n. Therefore i would say the correct answer is O(n^2).

Edit:

Having looked at the code a bit harder, i'm having doubts about that inner while loop being O(n). The amount of iterations is basically random, i'm not quite sure how that is expressed in big-O. I mean if the PRNG is particularly bad it could be stuck in a cycle and never terminate, and on those grounds i would say this doesn't qualify as a correct algorithm, since an algorithm has to terminate at some point. Someone tell me why i am wrong?

Originally Posted by oogabooga

The inner loop is a little tricky, since it has a "random" factor in how many times it repeats.

What's so tricky about it? We have an even distribution. Average value will be n/2. Complexity of the loop O(n)

The number of iterations of the inner loop follows the binomial selection with replacement probabilities.
E.g. 4 items.
First time through outer loop, we have 0% chance of entering the inner loop.

Second time through the outer loop, we have a 25% chance of entering the inner loop, and for subsequent iterations. The chance of exactly N iterations is:
(0.25^N * 0.75)*100
E.g.
75% chance of requring no inner loop iterations.
18.75% chance of requiring one inner loop iteration.
4.6875% chance of two iterations.
You can see that the chance of iterating again diminishes very rapidly.

Third time through the loop, we are half-filled and the chance of exactly N iterations is:
(0.5^N * 0.5)*100
E.g.
50% chance of requring no inner loop iterations.
12.5% chance of requiring one inner loop iteration.
6.25% chance of two iterations.

Last time through the loop, the chance of exactly N iterations is:
(0.75^N * 0.25)*100
E.g.
25% chance of requring no inner loop iterations.
18.75% chance of requiring one inner loop iteration.
14.0625% chance of two iterations.

At half-full, you can see that the average number of iterations is still only about one half. It does get high as the end nears. For the last item I think it's fairly clear than it will require on average N/2 iterations to find the hole, but even the one before that will only require about N/4 iterations, so it's not that bad.

The exact math to prove it escapes me right now, but I believe that the correct answer is that it's actually O(n) average case overall for the whole function.

O_o

This strikes me as being "O(3n)" which is just "O(n)". (The `fill' and the `for' each being "O(n)" while on average the`while' only approaches "O(n)".)

Soma

fill is presumably linear complexity, judging from its name.

The `fill' and the `for' each being "O(n)" while on average the`while' only approaches "O(n)".

*derp*

Well, that would actually be "O(n * log n)".

*shrug*

Drunk at the wheel...

Soma

Originally Posted by phantomotap

*derp*

Well, that would actually be "O(n * log n)".

*shrug*

Drunk at the wheel...

Soma

I could see why this would be the case if the inner loop was O(log n), but according to iMalcs rather detailed reply earlier in this thread it seems it is actually O(n) thus making the total O(n^2), where is this O(n log n) coming from?

I could see why this would be the case if the inner loop was O(log n), but according to iMalcs rather detailed reply earlier in this thread it seems it is actually O(n) thus making the total O(n^2), where is this O(n log n) coming from?

O_o

My statement may be right or wrong, but it has nothing to do with what iMalc posted.

I was simply correcting a flaw in my own statement; with my logic, the inner loop essentially misses according to the binary logarithm of the filled slots scaled by a, nearly, constant factor. (The constant factor would be ignored with "Big O".) I had removed the entire scaling factor in my original thoughts ("O(n)") instead of just the constant ("O(n * log n)").

Also, you misunderstood what iMalc posted; if what iMalc shows is entirely accurate, that would make the entire process, a call to `permute', "O(n)" not "O(n^2)".

Soma

Best case: O(n) (inner loop never gets executed)

Worst case:
EDIT:Worst case is that it never terminates.

Because the worst case is worse than the best case, the average is surely more than O(n), but maybe by a small power >1 of N.

Originally Posted by King Mir

Best case: O(n) (inner loop never gets executed)

Worst case:
EDIT:Worst case is that it never terminates.

Because the worst case is worse than the best case, the average is surely more than O(n), but maybe by a small power >1 of N.

It is entirely possible for the expected or average case to match the best case. Particularly when the best base might be N operations and the average case might be 3N operations. Both are still O(n).

When you assume an even distribution, this problem turns into one of probabilities where each outcome is equally likely.
Let me state it more clearly: The whole thing is indeed O(n)
Those that arrived at the O(n*n) assumption have missed the fact that even when the boolean array is half filled, you still have a 50/50 chance of of hitting a false entry on your first random number. So when half filled you can expect an average case of half an extra iteration. Clearly it is nowhere near n/2 iterations on average, it only gets that bad for the very last item!

It's probably the same proof as the proof that escaped mathematicians for years where if you move half a metre in half a second, then a quarter of a meter in a quarter of a second, then an eighth of a meter in an eighth of a second etc etc, prove you actually end up reaching the 1 metre mark. The sum to infinity suggests that you don't, but in reality it is obvious that you are travelling at a constant speed. Along the same lines of whatever proof was eventually discovered for that, the inner loop here is amortised constant time.

Yes if the random number generator is extremely poor then it is possible for this to never terminate, but it would have to be so poor that certain numbers could never be generated at all, which is incomprehensibly non-random, and in all likelihood would not meet the C standard.