Sam Patel

Adding n items one by one is O(n log n). The bottom-up build is O(n). Here's the intuition. In a complete tree, about half the nodes are leaves, and leaves need no work. A quarter of the nodes sit one level up and can move down at most 1 level. An eighth can m…