Worst case analysis

• the worst case occurs when splitting leads to an empty part: