Explanation
1. Heap Sort for n Numbers
Heap sort is a comparison-based sorting algorithm that works by building a Binary Heap.
Building the Heap: Creating a max-heap or min-heap from an unsorted array takes O(n) time.
Sorting Phase: Extracting the root element (the maximum or minimum) repeatedly from the heap and restoring the heap property (heapify) takes O(logn) time per element. For n elements, this extraction phase takes:
(n−1)×O(logn)=O(nlogn)
Worst-Case Summary: In the worst-case scenario, every extraction requires shifting elements from the root to the leaf level. Thus, the total worst-case complexity remains:
O(nlogn)
2. Addition of Two n×n Matrices
Let A and B be two square matrices of dimensions n×n. The resulting matrix C=A+B is computed by adding corresponding individual entry elements:
Cij=Aij+Bijfor 1≤i≤n,1≤j≤n
Number of Operations: An n×n matrix contains exactly n×n=n2 individual elements.
Worst-Case Summary: Because you must loop through every row and every column to perform a single addition per element position, the total number of operations scales exactly with the size of the elements:
O(n2)
Final Conclusion
Combining both individual results in the precise sequence requested yields O(nlogn) and O(n2), which corresponds directly to option (a).
