Hola Luciana,
Primero veamos por qué con k operaciones se puede afectar como mucho 2k elementos distintos. Esto es porque una operación de unión como máximo puede afectar siempre 2 elementos nuevos, no afectados previamente. Por ejemplo, seleccionando cada vez 2 elementos en conjuntos individuales que no fueron afectados previamente. Cualquier otra operación afecta o 1 elemento nuevo, o todos elementos afectados previamente.
Ahora la pregunta que resta es, para cada elemento individual v, ¿cuál es la máxima cantidad de veces que se le puede cambiar su componente (al unirse a otra) luego de k operaciones?
Para eso vemos que el algoritmo consta en cambiar la componente del conjunto más chico. Es decir, que si v pertenece a la componente que le cambia el nombre, entonces la otra componente es al menos del mismo tamaño que la componente original de v (sino le cambiaríamos el nombre a la otra).
Entonces, si cada vez que le cambio el nombre a v su componente al menos se duplica en tamaño, hay que ver cuántas veces se puede duplicar el tamaño hasta llegar a 2k (que como es la máxima cantidad de elementos afectados por k operaciones, es también una cota superior para el tamaño máximo de la componente final). Como el tamaño de la componente de v al inicio es 1, es lo mismo preguntarnos cuántas veces tengo que duplicar 1 para llegar a 2k, y esa respuesta es log_2(2k), ya que 2^log_2(2k) = 2k.
En conclusión, si para cualquier nodo v, luego de k operaciones, solo puede cambiarse su componente log_2(2k) veces, entonces luego de k operaciones como máximo hay 2k * log_2(2k) cambios de componente total, que es O(k log_2(k)).
Si no quedó claro volvé a preguntar nomás.
Saludos,
Guillermo