# Why is Heapsort in O(n log n) if not all n operations take time log n?

let's consider that we already have constructed heap array.

so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap tree level decreases -> downheap operation level decreases

but nlogn means each n nodes has logn operation. But not all nodes do logn(original down heap operation level) operation because of heap tree level decrease.

• Note that it is "$O$" in $O(\log n)$. That is to say, it is an upper bound. – hengxin Apr 30 '17 at 3:00
• Recall the definition of asymptotic analysis — as a follow up, could you find a tighter upper bound for heap sort than $O(n \log n)$ knowing it's definition? – Nick Zuber Apr 30 '17 at 21:22

## 1 Answer

$n \log n$ means each $n$ nodes has $\log n$ operation.

No, it does not. That's like saying:

\$100 means I sold 100 drinks for \$1 each

Obviously, you could have sold any number of things as long as they add up to \$100. With algorithm costs it's the same. A sequence of operations taking "time"$\Theta(n \log n)$means that the "time" costs of all the operations add up to something that behaves roughly like$n \log n$. Once Landau terms enter the pickture, things get muddled. It's tempting to tread$\sum_{i=1}^n O(\log i)$in the same way as$\sum_{i=1}^n \log i\$, but the former sum doesn't really make sense. I recommend you read our reference questions on algorithm analysis and asymptotics to see how one can arrive at the final result here.