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.

  • $\begingroup$ Let's say I have to traverse the list one by one, starting from the first element. But, could I say something like: "Let S be the set of memory address of each node in the list", then, use CHOICE function to choose the right address? $\endgroup$ Dec 13 '14 at 17:42
  • $\begingroup$ I just don't know what is the power I have with this CHOICE function... I can use it with any set I want? $\endgroup$ Dec 13 '14 at 17:44
  • 2
    $\begingroup$ @VitorLima Sure, if you had the set of memory addresses in a list, you could choose from that. But how are you going to obtain that set without traversing the list? $\endgroup$ Dec 13 '14 at 18:25
  • $\begingroup$ So, this is the point, I have to supose I will build the set from the arguments I receive, right? Can't I just create the set I want and use CHOICE function ? $\endgroup$ Dec 13 '14 at 18:38
  • 1
    $\begingroup$ If you can explain how to create a set, you can certainly choose from it nondeterministically. If you can't create it, how could you possibly use it? $\endgroup$ Dec 13 '14 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.