Suppose we have elements 1, 2, ..., n, and perform a series of n^2 operations -
ID: 3865100 • Letter: S
Question
Suppose we have elements 1, 2, ..., n, and perform a series of n^2 operations - either UNION, FINDSET, or MAKESET - and n of them are MAKESET. This will be union by rank with path compression. What is the total amount of time spent? (There are two acceptable answers, just give one.) (a) Theta (n^2 lg n) worst case (b) O(n^2 lg n) average case (c) Theta(n^2) amortized case (d) O(n^2 lg* n) worst case (e) w(n^2 alpha(n)) n amortized case (f) Theta (alpha(n)) amortized case (g) Theta (n^2 alpha(n)) worst case (h) Ohm(n^2 lg n) average caseExplanation / Answer
option g.
There is standard theorem for this .
On a disjoint-set forest with union by rank and path compression, any sequence of m operations, n of which are MAKE-SET operations, has worst-case running time ¡ m(n) ¢
, where is the inverse Ackermann function. Thus, the amortized worst-case running time of each operation is ((n)). If one makes the approximation (n) = O(1), which is valid for literally all conceivable purposes, then the operations on a disjoint-set forest have O(1) amortized running time.