# Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i$

In heap (bubble down) we have the formula : $$\begin{eqnarray*} \sum_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum_{i=1}^{\log n}2^i -\log n\sum_{i=1}^{\log n}i\times2^i \\ & = & \log n\times2^{\log n+1}-(\log n\times2^{\log n+1}-(2^{\log n+1}−2)) \\ & = & 2n−2\in Θ(n) \end{eqnarray*}$$

1. Why we have $$\sum_{i=1}^{log(n)}(\log n - i)\times2^i$$ ?
2. How we get to $$2𝑛−2\in Θ(𝑛)$$ ?

1. $$(\log n - i)$$ counts the maximum number of swaps that a node may require, starting at level $$i$$, and descending to its final level; at most it could become a leaf. For instance if it starts at level $$0$$, then it could possibly require $$\log n$$ swaps; this would happen if the node placed at the root position becomes a leaf, since $$\log n$$ is the full height of the binary tree. And since level $$i$$ has up to $$2^i$$ nodes, $$(\log n - i)2^i$$ counts the maximum number of swaps for all nodes from level $$i$$, and $$\sum\limits_i (\log n - i)2^i$$ counts the maximum number of swaps for all nodes in the tree.
2. $$2n-2$$ is asymptotically $$\leq 2n$$ and $$\geq n$$; for instance $$n\geq 2$$ suffices. This is exactly the definition of $$\Theta$$.