Author: Andrew Wagner
Date: 12:39:49 02/27/05
I got to wondering this morning about Big-O notation for algorithms that depend
on some kind of random call. For example, suppose I want to output the natural
numbers from 1 to N, inclusive, in a random order, and I use this algorithm:
for (i = 1; i <= N; i++) {
k = random(); //assume this returns a number >= 1 and <= N
if (!ary[k]){ //assume this array contains N zeros to start with
ary[k]++;
printf("%d",k);
} else {
i--;
}
}
What is the efficiency of this algorithm in Big-O notation? Clearly the best
case is O(n). Intuitively, I would suspect worse case is infinity, but isn't the
probability of that happening 0?
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.