With siftDown() - $\bf O(n)$ линейная сложность

Нам дан массив. Для каждого элемента с середины до начала запускаем siftDown(). Сложность - $O(n)$. Почему не $O(n\log{n})$? Эта оценка тоже верна, но она слишком большая, на самом деле, она ниже , так как каждая процедура восстановления тут работает не $log(n)$. Доказательство в конце страницы.

Для min-heap

i = floor(n/2); 
while (i >= 0) {
	siftDown(i); 
	i--; 
}

Для max-heap:

Max-Heapify - по сути аналог siftDown() в Кормене

With siftUp() - $\bf O(n\log{n})$*

for (int i = n - 1; i >= 0; i--) {
	siftUp(i); 
}

*не точно, может быть другая сложность (n^2), но в любом случае асимптотика хуже, чем у первого способа

Доказательство O(n) первого способа