Worst Case Scenario in MaxHeapify

Question

First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most give a mathematical answer, but can't give a real example.

In CLRS 3ed pg 155 we have "The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the $\Theta(1)$ time to fix up the relationships among the elements $A[i]$, $A[LEFT(i)]$ , and $A[RIGHT(i)]$, plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i (assuming that the recursive call occurs). The children’s subtrees each have size at most $2n/3$ - $\textbf{the worst case occurs when the bottom level of the tree is exactly half full}$ — and therefore we can describe the running time of MAX-HEAPIFY by the recurrence $T(n) \leq T(2n/3) + \Theta(1)$.

I understand why the maximum nodes a subtree can have is around $2n/3$. I have two questions:

1) We're dealing with a heap - a "binary tree that is completely filled on all levels except possibly the lowest, which is filled from the left up to a point" (CLRS pg 151). For a given n, there's only one legal tree structure - we can't "make" its bottom level exactly half full. So what does it mean to say the worst run-time for n is when the bottom level is exactly full? If you mean that the worst-case happens when n is such that the bottom-level is half-filled, then it's worse in comparison to what? trees of other sizes? obviously different sizes have different run-times!

2) I understand why when there's a height difference it'll take another MaxHeapify call, but why does the bottom level have to be full? Can you give me an example of two trees of height larger than 1, where in one its bottom level is half-full, and in the other it's almost half-full (missing just one leaf from being half-full) and there's a worse run-time in the first one?

Answer 1

1) This is the worst case in regards to all the possible recurrences and their respective sub-problem sizes.

Let's take some small sample $n$'s for a tree of height $3$. This is to show how the varying worst-case sub-tree size ranges from 1/2 to 2/3.

$$ \begin{align} n &\quad \text{bottom half-full?} & \text{size of worst case sub-tree} \\ 8 &\quad no & 4/8 \\ 9 &\quad no & 5/9 \\ 10 &\quad no & 6/10 \\ 11 &\quad yes & 7/11 \\ 12 &\quad no & 7/12 \\ 13 &\quad no & 7/13 \\ 14 &\quad no & 7/14 \\ 15 &\quad no & 7/15 \\ \end{align} $$

We deal in worst case scenarios when defining running times. This is why we must look for the worst case sub-problem (sub-tree) to define the recurrence relation. Clearly with varying $n$ values, the recurrence would vary, so we must take the worst of them. This is clearly the result of the deepest level being half-full, resulting in the upper bound recurrence:

$$T(n) \leq T\left(\frac{2n}{3}\right) + \Theta(1)$$

Alternatively if we were looking for a lower bound, we should look for the best case of all those worst case sub problems. We could then achieve:

$$T(n) \geq T\left(\frac{n}{2}\right) + \Theta(1)$$

2) The heap with the bottom level half full will always have the worse running time no matter how trivial the difference is. Minor differences like the one you described are not important. We're not comparing for one instance, time complexity is used to compare on a larger scale. On a large scale you can see the size of the sub problem ranges from n/2 to 2n/3.

Answer 2

For a given algorithm, the running time can depend on the particular data configuration.

A worst-case scenario is one that corresponds to the maximum number of operations from all possible datasets. So the comparison is between executions from different datasets.