# Non-deterministic algorithm to check if a list has some given value

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 ?

If the only way you have to access the last element is to step through the whole list, one item at a time, you can't possibly use less than $O(n)$ time, even nondeterministically. If you used less than that, none of the paths through the computation would be able to access the end of the list, so none of them would be able to check whether it contained the desired entry.