1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – NMR-3
    Mar 29, 2018 at 14:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – quicksort
    Mar 29, 2018 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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