World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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 ?

#### Answered By : David Richerby

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.