Search code examples
arraysalgorithmtime-complexitylinear-search

Linear Search difference between O(1) and O(n)

I am confused with the following two cases in linear search. Let me write the linear search algorithm here first.

Pseudo code for linear search

input: unsorted array A & key

output: index i such that A[i] = key

LinearSearch(A,low,high,key) 
if high < low    
   return NOT_Found
if A[low] = key
   return low
return LinearSearch(A,low+1,high,key)

The complexity is O(n) in most of the book. What is the difference between

  1. Best-case runtime for linear search if key is present in the array [Ans: O(1)]
  2. Best-case runtime for linear search if key isn't present in the array [Ans: O(n)]

What is the reason that when the key is present in the array, the complexity will reduce to O(1)? Thank you very much!

Solution

  • Your question is based on the best case. The best case would be that your key is on the first position (O(1)). More practical would be the average case which is in both cases O(n)