CODEWITHSUNDEEP
disjoint-setsunion-find
alternative_chipmunk
alternative_chipmunk

Reputation: 1

proof of time complexity of union find with path compression

The Wikipedia page: wikipedia page states that

If m operations, either Union or Find, are applied to n elements, the total run time is O(m log*n).

The detailed analysis arrived at this result is :

enter image description here

My questions are:

  1. Shouldn't the sum be (m+n)log*n instead of mlog*n?
  2. Are the average time complexity for 1000 Find operations the same as the time complexity of each individual Find?

Upvotes: 0

Views: 1412

Answers (1)

soothsooth
soothsooth

Reputation: 173

Disclaimer: I'm still trying to understand these proofs myself, so make no claim to being an expert! I think I may have some insights though.

1) I think they have assumed that m = O(n), thereby making O((m + n)lg*(n)) into O(mlg*(n)). In Tarjan's original proof (of the inverse Ackermann function bound) (found here: https://dl.acm.org/doi/pdf/10.1145/321879.321884?download=true) he assumes that the number m of FIND operations exceeds n. In Introduction to Algorithms (CLRS - ch.21), the bound they prove is for m operations of which n are MAKE-SET. It seems like people are assuming that m will be asymptotically greater than or equal to n.

2) What they have proved is an amortized cost for each operation. This is an analysis technique which bounds to within a constant factor the time taken for a series of operations, from which you can trivially compute the average time per operation. There are several different ways to go about it (I believe this is an example of aggregate analysis?). It's worth looking into!

Upvotes: 0

Related Questions