Respuesta :
Answer:
Answers explained below
Explanation:
(a) Construction of a heap of size n , where the keys are not known in advance.
Worst Case Time complexity - O(n log n)
Two procedures - build heap, heapify
Build_heap takes O(n) time and heapify takes O(log n) time. Every time when an element is inserted into the heap, it calls heapify procedure.
=> O(n log n)
(b) Selection-sort on a sequence of size n.
Worst Case Time complexity - O(n^2)
Selection sort finds smallest element in an array repeatedly. So in every iteration it picks the minimum element by comparing it with the other unsorted elements in the array.
=> O(n^2)
(c) Merge-sort on a sequence of size n.
Worst Case Time complexity - O(n log n)
Merge sort has two parts - divide and conquer. First the array is divided (takes O(1) time) into two halves and recursively each half is sorted (takes O(log n) time). Then both halves are combines (takes O(n) time).
=> O(n log n)
(d) Radix sort on a sequence of n integer keys, each in the range of[ 0 , (n^3) -1]
Worst Case Time complexity - O (n log b (a))
b - base of the number system, a - largest number in that range, n - elements in array
Radix sort is based on the number of digits present in an element of an array A. If it has 'd' digits, then it'll loop d times.
(e) Find an element in a red-black tree that has n distinct keys.
Worst Case Time complexity - O (log n)
Red-black tree is a self-balancing binary tree => The time taken to insert, delete, search an element in this tree will always be with respect to its height.
=> O(log n)
