$ ./guess_the_languageProblem Solving — fill the blank
Problem Solving — fill the blank · hard · #293

What goes in the blank?

# heapify: sift down from the last parent to the root
for i in range(n // 2 - 1, -1, -1):
    sift_down(a, i)
# total time: O(____)

Answer: n (also accepted: n)

Most nodes sit near the bottom and sift only a little, so bottom-up heap construction sums to O(n), not O(n log n).
Play Problem Solving ▸