Note: first part is all context to question labeled "The Question" below:

Working through the CLRS Introduction to Algorithms, 3rd ed, in Chapter 6.4 as they are talking about heaps they state:

Each call to MAX-HEAPIFY costs $O(lg\ n)$ and BUILD-MAX-HEAP makes $O(n)$ such calls.

Ok, I'm with them, the running time for for BUILD-MAX-HEAP is therefore $O(n\ lg\ n)$, they go onto say:

This upper bound, though correct, is not asyptotically tight.

I understand this as well because really MAX-HEAPIFY doesn't operate on $lg\ n$ levels each time it's called, but rather it operates on $h$ levels where h is the height of the node it was called on. So they state:

Our tighter analysis relies on the properties that an $n$-element heap has height $\lfloor lg\ n \rfloor$ and at most $\lceil n/2^{h+1}\rceil$ nodes of any height $h$.

Ok, with them still as I know the entire tree has size $n$ nodes which is really using that formula when height=0: $n/2^0 = n$.

The time required by MAX-HEAPIFY when called on a node of height h is $O(h)$ and so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by:

$\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} \lceil {\frac{n}{2^{h+1}}} \rceil O(h) = O(n\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} {\frac{h}{2^{h}}})$

The question

Here's where I'm lost, I don't get how the $^{+1}$ disappeared on $2^{h+1}$. Is that some type of unwritten assumption that can be made when you place the equation within the Big-oh? Or because they eliminated the ceiling function?


$O(2^{n+1})=O(2\cdot 2^n)=O(2^n)$ since for any function $f(n)$ and constant $C>0$ we have $O(C\cdot f(n))=O(f(n))$.

  • $\begingroup$ Gadi, thanks I guess I have to get better used to some of the Big-oh intuition they seem to take for granted in the book. Follow-up question: They state they can use the following "identity" (my word) to solve the equation: $\displaystyle\sum_{k=0}^{\infty} kx^{k} = {\frac{x}{{1-x}^{2}}}$ And then proceed to solve the whole thing by letting $x=1/2$. That seems a bit arbitrary to me... $\endgroup$
    – ThaDon
    May 22 '11 at 21:44
  • $\begingroup$ bottom portion should actually read $(1-x)^2$ $\endgroup$
    – ThaDon
    May 22 '11 at 21:57
  • 1
    $\begingroup$ This is a well-known basic combinatorial/analysis result - it involves the geometric sum \sum x^n which defines the 1/(1-x) function for |x|<1, and then differentiating it. $\endgroup$
    – Gadi A
    May 22 '11 at 22:06
  • $\begingroup$ The switching to $\frac{x}{(1-x)^2}$ I can accept, but I don't get the "let x=1/2", that's the part I found arbritrary. Did they just pick it because it reduced nicely to 2? $\endgroup$
    – ThaDon
    May 22 '11 at 23:03
  • 1
    $\begingroup$ No, they were trying in the first place to calculate the sum $\sum_{k=0}^\infty k(\frac{1}{2})^k$ - they just noted "hey, this sum is exactly what you get when you substitute x=1/2 in this general series!" $\endgroup$
    – Gadi A
    May 23 '11 at 4:11

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.