# How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ξ©(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williamsβ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]" we can also know if we build the heap using other methods. the big O could be better. Where should we begin if we would like to prove that the performance, Big Omega ,of building a binary heap using recursive method is Ξ©(nlog(n)), which is same as Big-O?

insert method from wiki

To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, swim-up, heapify-up, or cascade-up), by following this algorithm:

Add the element to the bottom level of the heap. Compare the added element with its parent; if they are in the correct order, stop. If not, swap the element with its parent and return to the previous step

then we have the buildheap as

buildheap((π1,πΎ1),(ππ,πΎπ))
if n==1:
return [(π1,πΎ1)]
return insert((ππ ,πΎπ),buildheap((π1,πΎ1),...(ππβ1,πΎπβ1))

• The first step is to define the problem formally. Are you trying to prove a lower bound on the worst case complexity of a particular algorithm ("recursive method")? Perhaps you're looking for a lower bound for an algorithmic task ("building a binary heap")? In the former case, you should describe the algorithm, and in the latter, the problem you are interested in. Commented Sep 15, 2019 at 6:43
• @YuvalFilmus, is this more clear ?
– mmmm
Commented Sep 16, 2019 at 3:39
• You need to give an input on which the algorithm takes $\Omega(n\log n)$ steps. Commented Sep 16, 2019 at 7:39

Suppose that your heap is a max-heap: a parent should be larger than its children. Consider what happens when you call buildheap with the numbers $$1,\ldots,n$$ in that order. Each time you add a new element to the bottom level of the heap, and the heapify procedure diffuses it all the way to the root. Since element $$k$$ is put at level $$\Theta(\log k)$$, inserting the $$k$$'th element takes time $$\Theta(\log k)$$. Overall, buildheap takes time $$\Theta(\log 1 + \cdots + \log n) = \Theta(\log n!) = \Theta(n\log n)$$.
• Element 1 is put at level 0. Elements 2,3 are put at level 1. Elements 4,5,6,7 are put at level 2. More generally, elements $2^d,\ldots,2^{d+1}-1$ are put at level $d$. Commented Sep 16, 2019 at 18:11