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))
    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.

  • 1
    $\begingroup$ 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? $\endgroup$ – 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$).

The second question is a reasonable exercise, so I'll let you solve it yourself. A hint: you might want to review the definition of average-case complexity. Also, you might want to compute the probability that this function returns on the first iteration, and you might want to review the expected value of a geometric random variable.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.