> 1 random generation per element, vs. log(n) or log(u)
The expected height of an element is 2, and the maximum height is 32. So there is at most a constant-factor performance difference, and in practice we should find this constant to be small.
It's not clear whether any small performance gain is worth the loss of clarity in presentation of the algorithm and code.
Not only that, but if you were to write this in (say) Java, which uses a linear congruential random number generator, doing it this way would probably be even faster due to the higher quality random numbers. The least significant bits on a linear congruential generator aren't terribly random.
The expected height of an element is 2, and the maximum height is 32. So there is at most a constant-factor performance difference, and in practice we should find this constant to be small.
It's not clear whether any small performance gain is worth the loss of clarity in presentation of the algorithm and code.