I know that I can build a non-deterministic algorithm with a
CHOICE function that verifies if a value
x is in an array in O(1) time complexity.
The usual algorithm to do that is
find (A, x) j = CHOICE(1, .. , A.length) if A[j] == x return VALID return FAIL
But, it works because we are able to access the position
j directly, in constant time.
So, if I change the problem: instead of an array A, use a linked-list L, then, how can I construct my non-deterministic algorithm using the
CHOICE function to check if a value
x is in L or not ?
Will it still have O(1) time complexity ?