3
$\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?

$\endgroup$
  • $\begingroup$ see this cs.stackexchange.com/questions/71547/… $\endgroup$ – aaag Aug 17 '17 at 10:03
  • $\begingroup$ Are you aware of the definition of expected values? $\endgroup$ – Raphael Aug 17 '17 at 13:18
  • $\begingroup$ @Raphael, probably not, is that relevant here? $\endgroup$ – Maxim Koretskyi Aug 17 '17 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 Aug 17 '17 at 13:31
  • $\begingroup$ @Raphael, thanks, I'll also read about it $\endgroup$ – Maxim Koretskyi Aug 17 '17 at 13:54
5
$\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}$$

$\endgroup$
  • $\begingroup$ got it, thanks, so why is it often stressed that the array should be randomly distributed? $\endgroup$ – Maxim Koretskyi Aug 17 '17 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 Aug 17 '17 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 Aug 17 '17 at 10:13

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