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