What does $O(\alpha(n))$ amortized time mean?

Question

DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect.

from a set of consectutive integers like $S = \{1,2,3,5,6\}$

Provide a data structure and an algorithm for DELETE that takes $O(\alpha(n))$ amortized time

---

not sure what what does $O(\alpha(n))$ amortized time mean?

I was thinking AVL trees ? I know the worst case is $O(\log n)$ for that. Not sure what $O(\alpha(n))$ amortized time means though.

Answer 1

$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$.

In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, which are pretty much the fastest data structures you'll ever use.

EDIT: $^nb$ indicates "tetration", that is, iterated exponents. It grows ridiculously quickly: $O(^n2)$ is worse than $O(n!)$.

Answer 2

$\alpha(n)$ is the inverse Ackerman function.