World's most popular travel blog for travel bloggers.

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

, , No Comments
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 ?

Asked By : Vitor

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback