1. Problem statement: We analyze a complete binary tree T of size $n$ where the last level is filled from left to right. (a) Number of nodes at height $h$: In a complete binary tree, height $h=0$ corresponds to leaves, and height increases up to the root. The number of nodes at height $h$ is the number of nodes in the subtree at that height. For height $h$, the number of nodes is roughly the number of nodes on level $L - h$, where $L$ is the tree height. Since the tree is complete, number of nodes at height $h$ is about: $$\text{nodes}(h) = \lceil \frac{n}{2^{h+1}} \rceil$$ This holds for $h \geq 0$. (b) Bubble-Down running time and total at height $h$: The Bubble-Down operation on a node at height $h$ takes time proportional to $h$ since it compares and potentially swaps down along the path of length $h$. Thus: $$\text{time}_{\text{BubbleDown}}(h) = O(h)$$ Applying Bubble-Down to all nodes at height $h$: Number of nodes at height $h$ is approximately $\frac{n}{2^{h+1}}$, so total time is: $$\text{total}_h = O\left(h \cdot \frac{n}{2^{h+1}}\right)$$ Because nodes are fewer at higher heights, the factor $\frac{n}{2^{h+1}}$ decreases exponentially. (c) Prove Heapify is $O(n)$: Total time is the sum over all heights: $$\text{total} = \sum_{h=0}^{\log n} h \cdot \frac{n}{2^{h+1}} = n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}}$$ Rewrite sum: $$= \frac{n}{2} \sum_{h=0}^{\infty} \frac{h}{2^{h}}$$ Using hint: $$\sum_{x=0}^\infty \frac{x}{2^x} = 2$$ So: $$\text{total} = \frac{n}{2} \times 2 = n$$ Therefore, the time complexity of Heapify is $O(n)$. This shows the linear time complexity of Heapify due to decreasing work at higher levels balanced by the increasing cost $h$ per node.