Изменения

Предположим, что мы вставляем <tex>i+1</tex>-ую точку из последовательности из <tex>n</tex> точек. Рассмотрим все перестановки из этих <tex>i+1</tex> точек, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>. Тогда средняя степень последней вершины среди перестановок равна: <tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1, v_2, ..., v_{i+1})} \operatorname{deg} (p[i+1])} {(i+1)!}</tex> Каждая из <tex>i+1</tex> вершин побывает последней ровно <tex>i!</tex> раз, поэтому: <tex>E(\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k)} {(i+1)!} = \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+1} = \frac {O(i+1)} {i+1} = O(1)</tex> {{TODO|t=proofКак сделан переход от степеней вершин к O-шкам?}}