Search code examples
algorithmsortingheapheapsort

How did CLRS book conclude BUILD_MAX_HEAP is not asymptotically tight with O(n log n)?

enter image description here

CLRS book page no 157 3rd edition. My question is not regarding why is complexity of BUILD_MAX_HEAP is O(n) nor the proof. However, towards the systematic approach they used to conclude that it is not asymptotically tight at O(n log n). Logically it is right to say O(n log n).

The point i’m stuck is how did they get the intuition that, there is much better tighter upper bound. If it wasn’t for the CLRS explanation. Will we ever know ?

The core of my question regarding the intuition we have to make self aware that there is a much better tighter bound.

Are we suppose to hunt for tighter tighter bound for every algorithm we find ? I mean a logical conclusion for a laymen is O(n log n). How can he go further from here. Have i missed some basics in between ?

Solution

  • how did they get the intuition that, there is much better tighter upper bound.

    I don't know how did they specifically get the intuition, but here is one way of seeing it (possibly with the benefit of hindsight).

    Build-Heap's complexity, at least intuitively, seems similar to

    T(n) = T(n / 2) + Θ(n)

    whose solution is T(n) = Θ(n).

    (Note that what follows is not a proof, but only intuition!)

    Say you have a binary heap with n / 2 elements, and whose last row is full, and you double the number of elements. This will basically add another row.

    How does doubling the number of elements (in this case, at least), change the time of Build-Heap?

    • Because of the penultimate row, there are Θ(n) more calls to Heapify, but each one obviously does O(1) work.

    • For the rows above the penultimate row, the Θ(n) calls to Heapify basically operate as before, but each one has another O(1) work at the end (the path is longer by 1).

    Are we suppose to hunt for tighter tighter bound for every algorithm we find ?

    To some extent, yes. Finding tighter bounds for algorithms always generates interest. Note that for Heapsort, there was even interest in proving that one variation used 2 n log(n) (1 - o(1)) operations, whereas another one used n log(n) (1 + o(1)) operations, even though both are Θ(n log(n)).

    I mean a logical conclusion for a laymen is O(n log n).

    Laymen probably mostly use algorithms which have been extensively studied by experts.

    How can he go further from here.

    There's probably no algorithm for finding bounds on algorithms. One possible approach would be to plot the running time for increasing values of n, and see how the running time looks. If it looks linear, it's not a proof, but it's an indication for what to look for.