Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Disjoint Sets as SLLs
#1
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!
Reply
#2
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.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)