1
$\begingroup$

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n

If we have a search algorithm like so:

while true:
  i := random(1, n)
  if A[i] == x
    break

random(a,b) picks a number uniformly from a to b

From this we know that the chances of finding x and terminating the program is k/n with each iteration. However what I would like to know is what would be the expected value for the number of iterations or more specifically the amount of times the array was accessed in this program given the array A as described above.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let $N$ be the geometric R.V. that returns the number of times the array was accessed in order to search for the element, $A[x]$ until we successfully find it. We want to know $\mathbb{E}[N]$.

We can view the iterations of the while loop as a sequence of IID Bernoulli trials, each with a probability $p$ of succeeding, and $q = 1 - p$ of failure. Given the question, we want to know how many trials are needed to obtain a "success" which would be finding the element $A[x]$ thus the while loop terminates.

Since the $\Pr\{N = k\} = q^{k-1}p$, we have that $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \: q^{k-1}p$.

Thus, $\mathbb{E}[N] = \dfrac 1p$ where $p = \dfrac kn$ so $\mathbb{E}[N] = \dfrac nk$.

So on average, it takes $\dfrac nk$ accesses before we find the element, $A[x]$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.