Design an algorithm for performing sequential or linear search and compute best case worst case and average case efficiency

In this post we are discussing about Design an algorithm for performing sequential or linear search and compute best case worst case and average case efficiency

Algorithm :-

Algorithm sequentialsearch(A[0. . . n-1] , k)
{
// Searches for a given value in a given array by sequential search
// input: An array A[O... n — 1] and a search key K
// Output: The index Of the first element in A that matches K
// or —1 if there are no matching elements
i <- 0
while i < n and A[i] != K do
     i <- i+1
if i < n 
    return i
else 
    return —l

Efficiency Analysis:

• Best Case: The best-case scenario occurs when the target key is found at the beginning of the array (index 0). In this case, the algorithm performs only one comparison, and the time complexity is O(1) or constant time. This is the most efficient situation.
• Worst Case: The worst-case scenario happens when the target key is either not in the array or is located at the very end of the array (or not present at all). In this case, the algorithm performs n comparisons, where ‘n’ is the number of elements in the array. The worst-case time complexity is O(n) or linear time.
• Average Case: The average-case time complexity is also O(n). This is because, on average, you would expect to search halfway through the array before finding the key (assuming the key is equally likely to be anywhere in the array). So, you perform approximately n/2 comparisons on average.