Question

1. Argue that the problem, H, of creating a MIN-HEAP from an unsorted array of integers using the HEAPIFY algorithm discussed in class is at least as hard - and maybe even harder - than the problem, M, of finding the minimum element of the same unsorted array of integers.

Answer 1

Problem H and problem M can be compare on the basis of complexity,the problem which is having worst complexity is harder then the second one.

For problem H:

Algorithm :
1. Build a min heap from the input data.
2. At this point, the smallest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.

Time complexity:It takes O(logn) for heapify and O(n) for constructing a heap. Hence, the overall time complexity of heap sort using min heap or max heap is O(nlogn).

For problem M:

Searching linearly: Increment the loop by 1

We initialize minimum element to the first element and then traverse the array, comparing each element and update minimum whenever necessary.

Time complexity = O(n), Space complexity = O(1)

Here problem H having time complexity 0(nlogn)for creating a min heap using unsorted array ,for the same unsorted array finding the min element problem M ,having time complexity 0(n). Means problem H is much harder then the problem M on the basis of their time complexity.