Consider the quick-union algorithm for disjoint sets. We know that a sequence of n operations (unions...

 

Transcribed Image Text:

Consider the quick-union algorithm for disjoint sets. We know that a sequence of n operations (unions and finds) can take asymptotically slightly more than linear time in the worst case. [a] Explain why if all the finds are done before all the unions, a sequence of n operations is guaranteed to take O(n) time. [b] Explain why if all the unions are done before all the finds, a sequence of n operations is guaranteed to take O(n) time. * Consider the quick-union algorithm for disjoint sets. We know that a sequence of n operations (unions and finds) can take asymptotically slightly more than linear time in the worst case. [a] Explain why if all the finds are done before all the unions, a sequence of n operations is guaranteed to take O(n) time. [b] Explain why if all the unions are done before all the finds, a sequence of n operations is guaranteed to take O(n) time. *