3 edited tags; edited tags
2 deleted 1 character in body

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $$\frac{n}{2}$$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $$n$$ cases corresponding to when the target value is the $$1$$st, $$2$$nd, ..., $$n$$th entry of the list. There is also the casescase where the entry is not in the list at all, so we have $$n + 1$$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $$1, 2, \dots, n$$ comparisons respectively. For the case where the target value is not in the list, we need $$n$$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $$\frac{n}{2}$$.

May I where is the fallacy in my reasoning? Thank you!

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $$\frac{n}{2}$$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $$n$$ cases corresponding to when the target value is the $$1$$st, $$2$$nd, ..., $$n$$th entry of the list. There is also the cases where the entry is not in the list at all, so we have $$n + 1$$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $$1, 2, \dots, n$$ comparisons respectively. For the case where the target value is not in the list, we need $$n$$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $$\frac{n}{2}$$.

May I where is the fallacy in my reasoning? Thank you!

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $$\frac{n}{2}$$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $$n$$ cases corresponding to when the target value is the $$1$$st, $$2$$nd, ..., $$n$$th entry of the list. There is also the case where the entry is not in the list at all, so we have $$n + 1$$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $$1, 2, \dots, n$$ comparisons respectively. For the case where the target value is not in the list, we need $$n$$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $$\frac{n}{2}$$.

May I where is the fallacy in my reasoning? Thank you!

1

# Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $$\frac{n}{2}$$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $$n$$ cases corresponding to when the target value is the $$1$$st, $$2$$nd, ..., $$n$$th entry of the list. There is also the cases where the entry is not in the list at all, so we have $$n + 1$$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $$1, 2, \dots, n$$ comparisons respectively. For the case where the target value is not in the list, we need $$n$$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $$\frac{n}{2}$$.

May I where is the fallacy in my reasoning? Thank you!