For average segment size and a uniform distribution of false positives, the average penalty is k 2 , as described earlier.
the behavior at the edges of the segments remains the same, though, so the average penalty never reaches k. Now, consider what happens with smaller segments.