Heap Sort

Heap Sort
The running complexity of BuildHeap is O(n)
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
"Thus the lesson to be learned is that when designing algorithms that operate on trees, it is important to be most efficient on the bottommost levels of the tree (as BuildHeap is) since that is where most of the weight of the tree resides"

Another simple analysis:
we can skip half of the nodes at the height 0, which has n / 2 nodes
at height 1: n / 4 * 1
at height 2: n / 8 * 2
at height 3: n / 16 * 3
...
at height lgn: 1 * lgn

for bottom 3 levels: n / 4 + n / 8 * 2 + n / 16 * 3 = 11 / 16 * n
for bottom 4 levels: 11 / 16 + 4 / 32 = 13 / 16 * n
for bottom 5 levels: 13 / 16 + 5 / 64 = 47 / 64 * n
for bottom 6 levels: 47 / 64 + 6 / 128 = 100 / 128 * n
...
you can see that it will never be greater than n. That's why it is linear