# Best, worst and average cases for a function that uses random number generator

For the following function (not in particular coding style or programming languange)

f (N, y)                // y is an integer such that 0 <= y < N
{

x = rand (N)            // rand (N) returns a random integer x satisfying 0 <= x < N

if (y == rand (N))
return
else f (N, y)

}


I need to find best, worst and average cases using O-notation. So my assumption is that the line

x = rand (N)


does nothing particular but in each recursion it takes O(1) (correct me if my assumption is wrong).

Now, the best case is quite obvious - rand() will give y or O(1).

The thing that I have stuck in are the worst and average cases. In the worst case it will just go into infinite iteration, but what is the complexity for a function that does not halt? And what is the average case? My assumption about the average case is that it will go through all N integers and then find y.

• What have you tried? What do you know about average-case complexity? Do you know the definition of average-case complexity? Have you tried plugging it in? – D.W. Oct 30 '13 at 17:59

To answer your first question, the average-case complexity of an algorithm that does not halt is, well, infinite ($\infty$).