Non Deterministic Search Algorithm

Non Deterministic Search Algorithm is a way of searching elements from an array probabilistically.

• As discussed earlier, a non-deterministic algorithm operates in two-stage: guessing and verification.
• A non-deterministic search algorithm randomly guesses/selects an element from the given list in the guessing phase. And in the verification stage, it compares the selected number with the key to be searched.
• If guessed value and key are the same then the verification stage returns “Yes” otherwise process may be repeated.
• In a non-deterministic search algorithm, an index between 1 to n is generated randomly. If the key element is found on i-th index then the algorithm returns success, else returns false.
• Run the algorithm again and observe the output. As the index i is generated randomly, we might need to run multiple times before we get success.
• For the given example, the key to be searched is 44, and the random index generated is 4. The element in an array on index 4 is 55, which does not match with the key index and hence algorithm returns fail.
• On the right side of the figure, the generated random index is 2, and the key to be searched is 11. The element on index 2 in the array is 11, which matches the key element. And hence, the algorithm will return success.

Algorithm: Non Deterministic Search Algorithm

The non-deterministic algorithm for searching an element from the array is shown below :

Algorithm NON_DET_SEARCH(A, key)
// Description : Search element key from array A non-deterministically
// Input : Array A of size n and key to be searched
// Output : Success / Failure

// Guessing stage
i ← select(1, n)            

// Verification stage
if  A[i] == key then
“key is found on location”, i
    success()    // Successful search
fail()           // Unsuccessful search

• The non-deterministic algorithm described here uses three functions:
  • select : Non-deterministically guesses the index between 1 and n.
  • success : Indicates successful search.
  • fail : Indicates an unsuccessful search.
• Deterministic search performs n searches in the worst case. The non-deterministic algorithm randomly selects an index between 1 and n and checks if the key exists in that location.
• The complexity of the non-deterministic algorithm is a function of the selection of an element from the list. It runs in O(f(n)), where n is the size of the input list.

---

Youtube Channel: https://shorturl.at/inryW