Heapsort – Step 1

• in worst case, you need n/2 + n/4 + n/8 + ... + 1 steps to create the initial heap

• therefore Step 1 can be done in O(n)