Hi all,

I have a doubt about the asymptotic complexity of random loops. For instance, consider the loop:

while(x < rand()){
do something;
}

Is the complexity of this loop O(x), O(1) or even another?

Thanks in advance for your help.

With algorithms that involve randomness, you need to talk about the expected running time. Quicksort is a good example. The worst case run time is quadratic if you're extremely unlucky with the random numbers that you pick, but the expected running time is O(nlog(n)).

Interesting, my guess is that its complexity is inf, because in the worst case this can be an infinite loop. But I feel that I might be wrong. I would love to see other's comments.