I can't understand why the complexity of a weighted-union of disjointed sets with lists has complexity O(log n) for one Union and O(nlogn) for n unions.
I know that the complexity is based uppon the number of elements in which we have to adjust the pointer to the reppresentative of the set. With Weighted-union i mean the Union made appending the shortest list to the longest so we never reach the case where we append a list with n elements to a shorter one.
I tried to to draw the worst possibile case, the one where at every one of the n Union the length of the lists is the same, but I get stuck and just dont get O(log n), for example if I append a list of one element to another of one element, then a list of two elements to another o two elements, a list of four elements to another of four, I get that when appending a list of 4 or 8 elements I have to change 4 or 8 pointers and not log(8) = 3 or log(16)= 4 pointers.
That is not how a union is performed. First of all, the union operation does not work on lists, but on trees. Secondly, the union operation takes two elements, for which the disjoint set data structure has registered parent relationships to their respective parents in their respective trees. Then a traversal is made from these two tree nodes to the roots of the respective trees. Each of the two traversals takes steps, where is the depth of the node in the respective tree. A disjoint set guarantees that this is O(log), and so finding the respective roots is a O(log) operation. The next operation is to make one of these two roots a child of the other, so that you now have merged two trees into one tree. That is an O(1) operation, and so in total the operation is O(log).
In your example it is not true that 4 pointers are updated. Only one pointer is updated, and the other pointers indirectly point to the same root (via a parent path).