4
$\begingroup$

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the items in the list are randomly distributed.

Can anyone show how I would arrive at N/2 if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?

Improve this question
$\endgroup$
5
  • $\begingroup$ see this cs.stackexchange.com/questions/71547/… $\endgroup$
    – user35837
    Commented Aug 17, 2017 at 10:03
  • $\begingroup$ Are you aware of the definition of expected values? $\endgroup$
    – Raphael
    Commented Aug 17, 2017 at 13:18
  • $\begingroup$ @Raphael, probably not, is that relevant here? $\endgroup$
    – Max Koretskyi
    Commented Aug 17, 2017 at 13:23
  • $\begingroup$ Yes. See fade2black's answer. My feeling is that if you know that definition, the rest is pretty immediate. $\endgroup$
    – Raphael
    Commented Aug 17, 2017 at 13:31
  • $\begingroup$ @Raphael, thanks, I'll also read about it $\endgroup$
    – Max Koretskyi
    Commented Aug 17, 2017 at 13:54

1 Answer 1

Reset to default
7
$\begingroup$

First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the array we have already done $k$ comparisons.

If it is at $1$ then you find it in 1 comparison, if it is at $2$, you find it in 2 comparisons, $\dots$, if it is at $n$ then you do $n$ comparison in order to find it. In order to average it you sum the total number of comparisons $1+2+\dots + n = \frac{(n+1)n}{2}$ and divide it by $n$ (size of the array) resulting in $\frac{n+1}{2}$.

More formal proof: Assume that the input has uniform probability and the the size of the array is $n$. Let $X$ be a random variable denoting the number of comparisons. Then $p(X=x)$ will denote the probability that we do $x$ comparisons. Since the distribution is uniform, $p(X=x) =\frac{1}{n}$. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value $$E[X] = \sum_{x=1}^{n}{xp(x)} = \sum_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ got it, thanks, so why is it often stressed that the array should be randomly distributed? $\endgroup$
    – Max Koretskyi
    Commented Aug 17, 2017 at 9:48
  • $\begingroup$ @Maximus Notion of Average or expected number of steps has meaning only in context of some probability distribution. In other words, "array should be randomly distributed" means that input comes in a random way, i.e. if you know that input consists of positive integers between 1 and $n$ then randomly distributed means that any permutation on that integers is possible. In my answer I assumed that any permutation has equal probability, known as uniform distribution. $\endgroup$
    – fade2black
    Commented Aug 17, 2017 at 10:13
  • $\begingroup$ @Maximus For example if know that your input is always $1,2,3, 4,5,6,7,8,9,10$, then you don't need to search over all array. You just need to check if $x <1$ or $x>10$, if it is true then $x$ is not found, otherwise found. You just need only one comparison. This is an example of "lack" of randomness. $\endgroup$
    – fade2black
    Commented Aug 17, 2017 at 10:13
  • $\begingroup$ I think the probability of x being at position k is [ (1-(1/n))^(k-1) ] * (1/n), not just (1/n). $\endgroup$
    – payman
    Commented Nov 12 at 6:59

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