cs215 ยป

CS215 Unit 4 Solutions

CS215 Unit 4 Solutions: Heap

The running time for building a heap by inserting each element one at a time is \Theta(n \log n).

Each insertion is \log n because it runs one operation at each level of the heap and there are \log n levels in the heap.

There are n insertions.

Therefore the running time is \text{Time for each insertion} * \text{Number of insertions} = \Theta(n \log n).