3
$\begingroup$

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?

1 Answers 1

4

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

  • 0
    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...2011-05-22
  • 0
    bottom portion should actually read $(1-x)^2$2011-05-22
  • 1
    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.2011-05-22
  • 0
    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?2011-05-22
  • 1
    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!"2011-05-23
  • 0
    Gadi,thanks for all the help. I'm going to have to digest that last one. I didn't realize they were trying in the first place, calculate $\sum_{k=0}^\infty k(\frac{1}{2})^k$ Just gotta warm up the lightbulb some...2011-05-23
  • 0
    My prof explained the mysterious $x = \frac{1}{2}$, it's because $\left(\frac{1}{2}\right)^k = \frac{1}{2^k}$ which can also be represented as $2^{-k}$ to satisfy the use of $\sum_{k=0}^{\infty} kx^{k} = {\frac{x}{{1-x}^{2}}}$. I had to ask him a few times, as I'm super rusty with my algebra :( Luckily he's a patient man.2011-06-01
  • 0
    That's what I tried to say... Sorry for not being clearer.2011-06-02