$(30$ points$)$ Question $1$

Consider the following linear search algorithm that searches for a target element within an

array of numbers.

Function search$($array of size $n,$ target$)$:

for each element in array:

if element $==$ target:

return "Element found"

return "Element not found"

Analyze the best$-$case, average$-$case, and worst$-$case scenarios for this linear search algorithm

based on the position of the target element within the array.

a$)$ Best Case: What is the best$-$case scenario for this linear search algorithm? Explain the

situation where it would perform most efficiently.

b$)$ Average Case: How does the average$-$case scenario consider different possible positions

of the target element within the array? Provide an explanation of how the algorithm

performs on average.

c$)$ Worst Case: What is the worst$-$case scenario for this linear search algorithm? Describe

the input arrangement that would lead to the highest time complexity.