Before revision:  The second algorithm maintains an O(k)-approximate cut sparsifier of size \tilde  (n) in \tilde  (n^{1/k}) amortized update time, for any k\ge1, which is polylog(n) time when k=\log(n).
After revision:  The second algorithm maintains an O(k)-approximate cut sparsifier of size \tilde (n) in \tilde O (n^{1/k}) amortized update time, for any k\ge1, which is polylog(n) time when k=\log(n).