Describe how a linear search works. On average, how many comparisons must a linear search perform?

Linear search is a sequential search where we can search for an element in sequential order until a match found

Explanation:

Linear search works in sequential order so we need to compare the search element with each element in the list in sequential manner

let the list is 10,23,5,28,56,4,60

The element to found is 4.

we will start with 10 and compare goes on till the element 4 reaches. If 4 didn't find in the list then the search element is not in the list.

Worst Case Performance is o (n).

let we have 10 elements (n=10). Then in worst case if element is not there in the list or element is at the end of the list we have to make 10 comparisons.

So the Worst Case Performance is o (n).

Best Case Performance is o (1)

if the element found at first place itself then only one comparision is required in best case