Efficiency

Consider your implementation of Heap.sort from the previous section. Assume Java's PriorityQueue is implemented as Binary Heap, hence insertion/removal are $O(\lg n)$.

Exercise Complete the following table. Use Big-Oh notation to asymptotically describe time/space complexities.

	Time Complexity	Space Complexity	Input Space	Auxiliary Space
`Heap.sort`

Solution

We need a PriorityQueue: $O(n)$ auxiliary space.
$n$ inserts into PriorityQueue, each $O(\lg n)$, adds up to $O(n \lg n)$
$n$ removes from PriorityQueue, each $O(\lg n)$, adds up to $O(n \lg n)$

	Time Complexity	Space Complexity	Input Space	Auxiliary Space
`Heap.sort`	$O(n \lg n)$	$O(n)$	$O(n)$	$O(n)$