355
правок
Изменения
м
→Время работы
|id=flipnumberlemma
|proof=
Все флипнутые рёбра окажутся инцидентными вставленной точке(по лемме 8), а [[#deglemma|степень вершины — <tex>O(1)</tex> (по лемме 9)]]. Поэтому будет сделано <tex>O(1)</tex> флипов.
}}
Так как среднее число флипов — <tex>O(1)</tex>, то время вставки целиком зависит от времени локализации.
