Question 9 please.

6. Recall (from your COMP 2402 course) that there is a lower bound for sorting. Answer the following questions (a) What does it mean to have a lower bound for a problem? (b) State clearly what is the lower bound claim for sorting a set of n (real)-numbers. c) Why this claim does not apply to the problem in Question 5? 7. You are given an array A consisting of n real numbers. Describe and analyze an algorithm, running in O(n) time, that rearranges the elements of A so that A forms a binary heap. Once A is transformed into a Binary Heap, show how you can report the elements in A in sorted (ascending) order. How much time it takes to report all the elements of A in the sorted order? Justify your answer 8. You are given a set of n real numbers which you are asked to insert incrementally in an initially empty binary search tree. Note that the time to insert an element in a binary search tree of size z is O(log ar). What is the total running time of inserting all the n elements in the tree. Justify your answer. Assume that you have formed the binary search tree on n elements, show how you can report the elements in a sorted order in O(n) time 9. Reflecting on the answers to the previous two questions, is the construction of a binary heap in O(n) time or reporting the elements in sorted order from a binary search tree in O(n) time is in contradiction to the lower bound for sorting (refer to Question 6)? Justify your answer 10. Discuss a couple of scenarios where you will be using a binary heap instead of a binary search tree. Justify your answer 6. Recall (from your COMP 2402 course) that there is a lower bound for sorting. Answer the following questions (a) What does it mean to have a lower bound for a problem? (b) State clearly what is the lower bound claim for sorting a set of n (real)-numbers. c) Why this claim does not apply to the problem in Question 5? 7. You are given an array A consisting of n real numbers. Describe and analyze an algorithm, running in O(n) time, that rearranges the elements of A so that A forms a binary heap. Once A is transformed into a Binary Heap, show how you can report the elements in A in sorted (ascending) order. How much time it takes to report all the elements of A in the sorted order? Justify your answer 8. You are given a set of n real numbers which you are asked to insert incrementally in an initially empty binary search tree. Note that the time to insert an element in a binary search tree of size z is O(log ar). What is the total running time of inserting all the n elements in the tree. Justify your answer. Assume that you have formed the binary search tree on n elements, show how you can report the elements in a sorted order in O(n) time 9. Reflecting on the answers to the previous two questions, is the construction of a binary heap in O(n) time or reporting the elements in sorted order from a binary search tree in O(n) time is in contradiction to the lower bound for sorting (refer to Question 6)? Justify your answer 10. Discuss a couple of scenarios where you will be using a binary heap instead of a binary search tree. Justify your