50-70% as the worst case isn't even necessarily that bad.

(Again, a lot is O(log n) right?)