Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
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... –  ThaDon May 22 '11 at 21:44
    
bottom portion should actually read $(1-x)^2$ –  ThaDon May 22 '11 at 21:57
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. –  Gadi A May 22 '11 at 22:06
    
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? –  ThaDon May 22 '11 at 23:03
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!" –  Gadi A May 23 '11 at 4:11
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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