Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).

Stephen Alstrup Amir M. Ben-Amram Theis Rauhe

Published in: STOC (1999)

Keyphrases

extended abstract
worst case
average case
upper bound
np hard
lower bound
optimal solution
greedy algorithm
approximation algorithms
error bounds
space complexity
worst case analysis
running times
computational complexity
mistake bound
databases
online algorithms
complexity bounds