1
$\begingroup$

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))
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 15 at 6:43
  • $\begingroup$ @YuvalFilmus, is this more clear ? $\endgroup$ – momo mo Sep 16 at 3:39
  • $\begingroup$ You need to give an input on which the algorithm takes $\Omega(n\log n)$ steps. $\endgroup$ – Yuval Filmus Sep 16 at 7:39
0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ can you give a bit reasoning on " Since element 𝑘 is put at level Θ(log𝑘)", why is Θ, not O, and why log k? Θ means lower bound, why not just Θ(1), always at the right place ? $\endgroup$ – momo mo Sep 16 at 17:40
  • $\begingroup$ Big Theta isn't (just) a lower bound. I suggest reviewing the various notations of asymptotic analysis. $\endgroup$ – Yuval Filmus Sep 16 at 18:11
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 16 at 18:11
  • $\begingroup$ yes Big Theta gives both lower bound and upper bound. still "Since element 𝑘 is put at level Θ(log𝑘)" is not convincing enough. it seems like to me just a statement without any proofs/reasoning , (or I just missed something obvious) $\endgroup$ – momo mo Sep 16 at 23:31
  • $\begingroup$ Yes, that’s on purpose. It’s your exercise, after all. $\endgroup$ – Yuval Filmus Sep 16 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.