Final answer:
The worst-case time complexities for build-heap, extract-max, and insertion on a heap with n elements are O(n), O(log n), and O(log n) respectively, while operations on a disjoint set with path compression and union by rank feature near constant time complexity, with a set of m operations being O(m · α(n)).
Step-by-step explanation:
The question relates to the worst-case time complexity of various operations in heap and disjoint set data structures typically studied in computer science and algorithms.
- a) Build-heap on n elements: The worst-case time complexity is O(n).
- b) Extract-max on a max-heap with n elements: The worst-case time complexity is O(log n) because it requires both removing the max element and then restructuring the heap.
- c) Insertion onto a max-heap with n elements: The worst-case time complexity is O(log n), which is the time needed to insert the new element and then restore the heap property.
- d) Find-set in a disjoint set with path compression: Assuming union by rank and find with path compression, the worst-case time complexity is nearly O(1).
- e) Link in a disjoint set with path compression: The time complexity is O(1), as it is a simple operation of linking two representatives.
- f) Union in a disjoint set with path compression: It is a combination of link and find-set, resulting in a time complexity that is nearly O(1).
- g) m operations of union, find, and make-set: With n make-set operations at the start, using union by rank and find with path compression, the total time complexity for m operations is O(m · α(n)), where α(n) is the Inverse Ackermann function which grows very slowly and is considered nearly constant for all practical values of n.