02-14-2018, 05:09 PM

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!