Question

1. answer the following matching questions, assuming a program uses the linear search (not all choices are used and some are used twice)
2. if a list has n elements, how many elements need to be checked to determine that the desired element does not exist in the list?
3. if a list has n elements, in the best case, how many elements would the computer need to check before it found the desired element?
4. if a list has n elements, what would the average number of elements be that the computer would need to check before it found the desired element?
5. if a list has n elements, in the worst case, how many elements would the computer need to check before it found the desired element?

a. n
b. 1
c. n²
d. n/3
e. n/2

Explanation:

Step1: Analyze non - existence case

In linear search, to determine an element does not exist in a list of n elements, all n elements need to be checked.

Step2: Analyze best - case

In the best - case of linear search, the desired element is the first one, so only 1 element needs to be checked.

Step3: Analyze average - case

Assuming the element is equally likely to be at any position in the list, the average number of elements to check is $\frac{1 + 2+\cdots + n}{n}$. Using the sum formula for the first n positive integers $S_n=\frac{n(n + 1)}{2}$, the average is $\frac{\frac{n(n + 1)}{2}}{n}=\frac{n+1}{2}\approx\frac{n}{2}$ for large n.

Step4: Analyze worst - case

In the worst - case of linear search, the desired element is the last one, so n elements need to be checked.

Answer:

1. a. n
2. b. 1
3. e. n/2
4. a. n