1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

$\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!)$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.