0
$\begingroup$

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 Θ(𝑛)$ ?

Please explain details!

$\endgroup$
0
$\begingroup$

So I guess you are showing that an array can be made a heap in linear time.

  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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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