Comment by pkhuong

Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.