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)$ |