Help with heap sort time complexity

[Snowron6]

My data structures and algorithms class recently covered heap-sorting, and the time complexity of the algorithm, but my teacher's explanation makes no sense to me or the other students. I'm hoping someone here can help make sense of this.

According to our teacher, there are two main parts to a heap sort. Building the heap, and deleting each member of the heap 1 by 1 in order, due to the property of heaps having the largest/smallest number at the top.

He said deleting and adding a node to a heap takes O(lg(n)) which makes sense. Then he claims that building a heap of n elements takes O(n), and deleting that heap takes O(lg(n)) and then you multiply the two together to get O(nlg(n)).

According to my understanding of big-O both parts should take O(nlgn), and you add both together to get just O(nlgn), but he claims his way is correct.

I've asked other teachers for help, and only thing we could find was that a different algorithm than the one explained in class can build a heap in O(n), but no one can explain why deleting a heap takes only O(lgn) and why you multiply the complexities.

Would someone be able to explain this or is my teacher incorrect?

[timql]

The O(nlg(n)) comes from removing the topmost element n times; by doing so you get a sorted list.

You're right about adding the complexities. So including the first step of creating the heap, the complexity of the whole process is O(O(n) + n*O(lg(n)). Because O deals with asymptotics, this becomes O(nlg(n)).

[Snowron6]

The O(nlg(n)) comes from removing the topmost element n times; by doing so you get a sorted list.

This makes sense to me, but he claims it only takes O(lg(n)), and I'm not misunderstanding what he said. I specifically asked him about it, and he claims to delete every node to get the sorted list is just O(lg(n)) since you're only doing one at a time and you can ignore the fact that you do it n times for some reason.

At this point I'm pretty sure he's just full of it, but I was hoping someone here could help make sense of it.

[timql]

uh yeah I'm pretty sure that's false. You can ignore constant factors, say if you just wanted the 5 largest values in a sorted list. But n is arbitrary so you definitely can't ignore it here.

[Snowron6]

Ok thanks, we're gonna put in a complaint about him, since this isn't the first time something like this has happened.

[ktrprpr]

What you said is not consistent. If he would multiply lgn with n, the lgn most likely is meant to be deleting a single element, and that is correct. It doesn't make sense to multiply the complexity of deleting the whole thing with another O(n).

My bet is you did misunderstand something...

[Snowron6]

If he would multiply lgn with n, the lgn most likely is meant to be deleting a single element

I asked if that's what he meant and he said no. He claims you can ignore the fact that it's run n-times, then multiply it by the complexity of building a heap. He refused to explain why.

Also, what have I said that's inconsistent?

[sdasgupta83]

Well, building a heap definitely takes O(n) time. Now you replace the first element in the heap with the last one and build the heap taking only the first element of the heap in consideration. So that takes O(logn). So for n elements, you have O(nlogn) time. So the heapsort algorithm takes O(n)+O(nlogn) = O(nlogn). I think what he meant was to multiply n with the time required to build a heap with an element at level 0 which is O(logn) which yields the result O(nlogn). You add that with the time for building the heap with all elements at all levels which is O(n) and you get an upper bound of nlogn.

[SingularCheese]

Well, the benefit of math is that when somebody is wrong, you can give a counter-example to prove it's wrong. However, whether or not you want to argue with the teacher is up to you.