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 linex = 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.
Best, worst and average cases for a function that uses random number generator
algorithm analysis