Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Disjoint Sets as SLLs
In class it was mentioned that disjoint sets implemented as SLLs could be unioned in lg(n) time in the worst case, provided you union from the small list to the larger. I was wondering if this would be asymptotic runtime or if this is amortized because the more I think about it, the more it makes sense for it to be O(n) for any given union, since union(A, B) where num(A) = n, num(B) = m, n >= m would run in n/2 time, in the worst case, which is O(n). Let me know where I am going wrong here if I am, please!
You are right. It is the average. Take all the union operations and in the worst case, the average of their times is log n.

Forum Jump:

Users browsing this thread: 1 Guest(s)