In the book Handbook of Data Structures and Applications, section 5.2.5, (copy of the relevant section available here) about leftist queues, the author(s) state the following:

For the complexity analysis of of the initialization operation, assume, for simplicity, that n is a power of 2. The first n/2 melds involve max HBLTs with one element each, the next n/4 melds involve max HBLTs with two elements each; the next n/8 melds are with trees that have four elements each; and so on. The time needed to meld two leftist trees with 2 i elements each is $\mathcal{O}$(i + 1), and so the total time for the initialization is $$\mathcal{O}(n/2 + 2 (n/4) + 3(n/8) + \ldots) = \mathcal{O}(n\sum \frac{i}{2^i}) = \mathcal{O}(n)$$

However, it seems to me that the summation iterates from i = 0 to $\log(n)$: $\sum_{i=0}^{\log(n)}$. This means it varies based on n, which in turn means the algorithm doesn't achieve $\mathcal{O}$(n) time as claimed but instead $\mathcal{O}(n \sum_{i=0}^{\log(n)} \frac{i}{2^i})$ time.

Am I misunderstanding something? I've found other explanations online stating $\mathcal{O}$(n) time for this sort of mass initialization is possible, but this is the only proof I've found so far.

up vote 2 down vote accepted

The succession $a_i = 2^{-i}i$ is absolutely convergent.

In more elementary terms:

$$ \frac{n}{2} \le \sum_{i=1}^{\log n} \frac{ni}{2^i} \le n\sum_{i=1}^{\infty} \frac{i}{2^i} = n\sum_{j=1}^{\infty} \left( \frac{1}{2^j}\sum_{i=1}^{\infty} \frac{1}{2^i} \right) = 2n $$

  • I'm sorry, I don't quite see how that equality is derived. I understand how you go from summation until log to the infinite summation, but not how you go from there to the next step. I did stumble upon the fact that $\sum_{i=0}^{k-1} = 2 - \frac{k+1}{2^{k-1}}$ which can be discarded because of O notation (which I should've found earlier - my bad). – NMR-3 Mar 29 at 14:34
  • 1
    Let $S = \sum 2^{-i}$. You can rewrite $\sum 2^{-i}i$ as $S + S/2 + S/4 + \cdots$ (each $2^{-i}$ term appears $i$ times). This is a very common transformation, "stolen" from the theory of generating functions. – quicksort Mar 29 at 14:49

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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