Worst-case analysis of the set-union problem with extended backtracking

AbstractIn this paper, an extension of the well known set union problem is considered, where backtracking over sequences of Union operations is allowed. A data structure is presented which maintains a partition of an n-item set making it possible to perform each Union in O(lg lg n) time, each Find in O(lg n) time and allows backtracking over the Unions in O(1) time. Moreover, it is shown that the data structure can be slightly modified as to present an O(k + m lg n) time complexity on a sequence of k Unions and Backtracks and m Finds. The space complexity of both versions of such a data structure is O(n)