Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top