3

In CLRS on page 155, about max-heaps, the running time of max-heapify is described as T(n) = T(2n/3) + O(1).

I understand why the first recursive call is on a subproblem of size 2n/3 in the case where we have a nearly complete binary tree (always the case with heaps) in which the deepest level of nodes is half full (and we are recursing on the child that is the root of the subtree that contains these nodes at the deepest level). A more in depth explanation of this is here.

What I don't understand is: after that first recursive call, the subtree is now a complete binary tree, so the next recursive calls will be on problems of size n/2.

So is it accurate to simply state that the running time of max-heapify is described by the recurrence T(n) = T(2n/3) + O(1)?

Community
  • 1
  • 1
evianpring
  • 3,316
  • 1
  • 25
  • 54
  • 1
    I don't have my copy of CLRS with me now, but perhaps they meant to say T(n) ≤ T(2n / 3) + O(1)? Assuming T(n) is monotonic that would provide a conservative upper bound. – templatetypedef Jul 29 '16 at 13:04
  • Yes that would make sense to me @templatetypedef. And solving the recurrence either way gives a running time of O(n). – evianpring Jul 29 '16 at 16:26
  • 1
    @Jim Mischel The supposed duplicate question isn't exactly the same question. It is an explanation for the part of my question that I said I understand. The question is, after that initial calculation (for the first recursive call, and explained in that duplicate question), that calculation is not applicable anymore since the subtree in the recursive call is now a complete tree (not half full). – evianpring Jul 29 '16 at 16:28
  • This is a good observation if indeed a misprint. It's not listed in the errata. I don't see it in my edition, but if confirmed, it should probably be reported. https://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-3e.php – Lorem Ipsum Sep 30 '20 at 23:33

1 Answers1

2

Converting my comment to an answer: if you assume that T(n), the time required to build a max-heap with n nodes, is a nondecreasing function of n, then we know that T(m) ≤ T(n) for any m ≤ n. You're correct that the ratio of 2n / 3 is the worst-case ratio and that after the first level of the recurrence it won't be reached, but under the above assumption you can safely conclude that T(n / 2) ≤ T(2n / 3), so we can upper-bound the recurrence as

T(n) ≤ T(2n / 3) + O(1)

even if strict equality doesn't hold. That then lets us use the master theorem to conclude that T(n) = O(log n).

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065