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 ComplexitySpace ComplexityInput SpaceAuxiliary 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 ComplexitySpace ComplexityInput SpaceAuxiliary Space
Heap.sort$O(n \lg n)$$O(n)$$O(n)$$O(n)$