Author: Daniel Pineo
Date: 15:15:02 02/27/05
Go up one level in this thread
On February 27, 2005 at 15:39:49, Andrew Wagner wrote:
>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?
O(f(n)) is the set of all functions that provide an upper bound (to within a
constant factor) on the running time of your algorithm f for all n greater than
some constant. There are no such functions in this case, so your O(f(n)) is
just the empty set.
- Dan Pineo
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.