Efficiency

Describe the efficiency of PriorityQueue based sort using Big-Oh notation.

Consider your implementation of Heap.sort from the previous section. Assume Java's PriorityQueue is implemented as Binary Heap, hence insertion/removal are $\Omicron(\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: $\Omicron(n)$ auxiliary space.
$n$ inserts into PriorityQueue, each $\Omicron(\lg n)$ , adds up to $\Omicron(n \lg n)$
$n$ removes from PriorityQueue, each $\Omicron(\lg n)$ , adds up to $\Omicron(n \lg n)$

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

Data Structures

Efficiency