6. answer the following matching questions, assuming a program uses the linear search (not all choices are…

6. answer the following matching questions, assuming a program uses the linear search (not all choices are used and some are used twice)\n1. 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?\n2. 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?\n3. 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?\n4. 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?\na. n\nb. 1\nc. n²\nd. n/3\ne. n/2

6. answer the following matching questions, assuming a program uses the linear search (not all choices are used and some are used twice)\n1. 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?\n2. 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?\n3. 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?\n4. 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?\na. n\nb. 1\nc. n²\nd. n/3\ne. n/2

Answer

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