text: # 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
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}