线段扫描算法的性能是O((n+k)log n)，因为它会在扫描点处理时，对活动线段进行重排序。如果这一步需要超过O(log s)的时间，s是状态中的线段数目，那么整体性能将会退化到O(n2)。例如，如果线段状态只是简单地使用双向链表（一个能够快速找到前驱和后继线段的数据结构），那么由于需要在表中找到正确的插入位置，插入操作将会增加到O(s)。并且随着线段集S的增长，性能的退化需要引起更多的注意。
类似地，事件队列需要能够高效地查询某个事件点是否已经在队列中。使用基于堆的优先队列实现，在java.util.PriorityQueue中提供同样使得算法退化到O(n2)。我们不希望口口声声说是O(n log n)的算法，最后的实现却是O(n2)的性能！