# Having trouble calculating the asymptotic running time of MAX-HEAPIFY

I don't understand the $$T(2n / 3)$$ part in the recurrence relation for MAX-HEAPIFY in the book CLRS. There is another post that explains it but I can't realize it.

• Is it clear to you that $2n/3$ must be an upper bound to the size of the subtree you are recursing in? For an explanation of the constant cannot be lower than $2/3$ you can see this answer? If that's not clear, maybe you can be more explicit on what your confusion is Commented Jul 8, 2021 at 14:14
• @Steven I have seen the answer but I haven't understood it. No I can't understand why it's an upper bound.
Commented Jul 8, 2021 at 14:21
• I'll try to write an answer showing how you can prove that. Commented Jul 8, 2021 at 14:28
• @Steven Thanks.
Commented Jul 8, 2021 at 14:29

Suppose that you are running MAX-HEAPIFY on some vertex $$v$$ of a heap $$H$$. Then the subtree $$H_v$$ rooted at $$v$$ is also a heap. Let $$n$$ be the number of vertices of $$H_v$$.

Clearly if $$v$$ has no children or only one (left) children then $$T(n) = O(1)$$ so let's focus on the case in which $$v$$ has two children $$u$$ and $$w$$, where $$u$$ is the left child and $$w$$ is the right child. Let $$n_u$$ be the number of vertices in $$H_u$$ and $$n_w$$ be the number of vertices in $$H_w$$.

Clearly the worst case happens when we choose to recurse on the subtree with most nodes between $$H_u$$ and $$H_w$$. By the properties of the heap we know that $$n_u \ge n_w$$ so we can restrict ourselves to the case in which we recurse on $$H_u$$.

The question now becomes: how large can $$n_u$$ be compared to $$n$$?

To answer this question let $$h_v$$ be the height of $$H_v$$. We know that the height $$h_u$$ of $$H_u$$ must be $$h_v - 1$$. Moreover, the height of $$H_w$$ can be either $$h_v-1$$ or $$h_v-2$$ (otherwise $$H$$ was not a complete binary tree).

The maximum number of nodes in a binary tree of a generic height $$h$$ is at most $$2^{h+1}-1$$ (which corresponds to a perfect binary tree binary tree). This tells us that $$n_u \le 2^{h_u + 1} - 1 = 2^{h_v} - 1$$.

Moreover, the number of nodes in a complete binary tree of height $$h$$ is at least $$2^h$$ (where $$2^h - 1$$ nodes are from a perfect binary tree of height $$h-1$$ and there must be at least one node on the $$h$$-th level). This tells us that $$n_w \ge 2^{h_w} \ge 2^{h_v-2}$$.

We are now ready to find the maximum possible ratio between $$n_u$$ and $$n = n_u + n_w + 1$$.

\begin{align*} \frac{n_u}{n} &= \frac{n_u}{n_u + n_w + 1} \le \frac{n_u}{n_u + 2^{h_v-2} + 1} = 1 - \frac{2^{h_v-2} + 1}{n_u + 2^{h_v-2} + 1} \\ &\le 1 - \frac{2^{h_v-2} + 1}{2^{h_v-1} + 2^{h_v-2} + 1} = 1 - \frac{2^{h_v-2} + 1}{3 \cdot 2^{h_v-2} + 1} \\ & < 1 - \frac{2^{h_v-2} + 1}{3 \cdot ( 2^{h_v-2} + 1)} = 1 - \frac{1}{3} = \frac{2}{3}. \end{align*}

• Excellent. I understand now. My problem was indexing. You modified it in this new answer. Thanks.
Commented Jul 8, 2021 at 16:54
• We also get the same upper bound for MIN-HEAPIFY. Right? With the same proof.
Consider a tree $$\mathcal{T}$$ at root $$\mathcal{r }$$, and contain $$\mathcal{n}$$ nodes and $$\mathcal{h}$$ be height of $$\mathcal{T}$$ such that leaves are half full, so, without loss generality, suppose the left sub-tree $$\ell$$ of $$\mathcal{T}$$ is a full binary tree (i.e. leaves are half full).
(i) Now it's sufficient to show that ratio of $$\ell$$ to $$n$$ (i.e. $$\frac{|\ell|}{n})$$ is $$\frac{2}{3}$$.
Consequently the worst case of MAX-HEAPIFY happen when we recurse on $$\ell$$.
For showing (i), first of all, let the number of nodes in $$\ell$$ is: $$|\ell|=\sum_{i=0}^{\mathcal{h}-1}2^i=2^h-1$$ The number of nodes in $$\mathcal{R}:$$ $$|\mathcal{R}|=\sum_{i=0}^{\mathcal{h}-2}2^i=2^{h-1}-1$$ As a result $$n=|\ell|+|\mathcal{R}|+\mathcal{r }=|\ell|+|\mathcal{R}|+1=3\times 2^{h-1}-1$$ So $$\frac{|\ell|}{n}= \frac{2^{h-1}-1}{3\times 2^{h-1}-1}\leq \frac{2\times2^{h-1}}{3\times 2^{h-1}}=\frac{2}{3}.$$