What is the computational complexity of this task? The goal is to compute the number $x=\min(\Bbb N\setminus A)$, where $A$ is the input list and the complexity parameter is $n=|A|$ (which is finite).

This is a common problem when generating a unique identifier: you want a number that is not equal to any other in the "pool" of other identifiers. A simpler algorithm just takes $x=\max(A)+1$, and assuming that $A$ is represented as a list of length $n$, calculating this is $O(n)$. But this leaves "gaps" in the set (assuming we are adding these new numbers to the pool $A:=A\cup\{x\}$ repeatedly), and this can be undesirable. A "gap-filling" algorithm uses $x=\min(\Bbb N\setminus A)$ instead, but this is a more complex operation.

A lower bound on the complexity is of course $O(n)$, since one must at least observe the entire input. An upper bound is $O(n\log n)$, since we can sort the list $A$ into order, then just walk down the list until we find an $x$ such that $A(x)\ne x$.