Linear Search for 7 in $A=[3,5,2,8,7,1,4]$

Algorithm

LinearSearch(A, n, key):
  for i=0 to n-1:
    if A[i]==key: return i  // 0-based index, +1 for 1-based position
  return -1 // not found

Trace for key=7

i (0-based)	A[i]	Compare A[i]==7?	Action
0	3	3==7? No	continue
1	5	5==7? No	continue
2	2	2==7? No	continue
3	8	8==7? No	continue
4	7	7==7? Yes	return 4 (0-based) / 5 (1-based)
Search stops early; elements after index4 not examined.

Result: Found at index 4 (0-based) → position 5 (1-based). Comparisons = 5 best/worst?

Complexity Analysis ($n=7$)

• Time:
  • Best $O(1)$ (key at first position)
  • Worst $O(n)$ (key absent or at last) → here worst would be 7 comparisons
  • Average $O(n)$ → expected $(n+1)/2$ if key present uniformly
  • In this instance 5 comparisons = $\Theta(n)$ worst-like.
• Space: $O(1)$ auxiliary (loop variable + key), $O(n)$ total if counting input array; in-place.
• No sorting needed; works on unsorted arrays; optimal for unsorted (any algorithm must examine $\Omega(n)$ in worst case).