Hi,

I have a couple of questions. What is meant by "running time"? Is that big O notation?

I need to find the running time of heapsort on an array of n elements that is already sorted in increasing order.

Is this a trick question? I did an example, 1, 2, 3, 4, 5, 6, 7, 8, 9 as my dataset.

Even though it is sorted, you will still need to heapify the data (max heapify), and Heapify is O(n log2 n). Then each type you extract the max item, you need to correct the heap.

So it still stays O(n log2 n). That's why I'm wondering if my understanding of what "running time" means is off.