According to the author of nrand -
There is no fixed, finite bound on the worst-case execution time of this program, but it terminates with probability 1 and its average performance is O(1). I strongly doubt it is possible to do any better.
gg