title: Linear Search difference between O(1) and O(n)
body: <p>I am confused with the following two cases in linear search. Let me write the linear search algorithm here first.</p>
  
  <p>Pseudo code for linear search</p>
  
  <p>input: unsorted array A &amp; key</p>
  
  <p>output: index i such that A[i] = key</p>
  
  <pre><code>LinearSearch(A,low,high,key) 
  if high &lt; low    
     return NOT_Found
  if A[low] = key
     return low
  return LinearSearch(A,low+1,high,key)
  </code></pre>
  
  <p>The complexity is O(n) in most of the book. What is the difference between </p>
  
  <ol>
  <li>Best-case runtime for linear search if key is present in the array [Ans: O(1)]</li>
  <li>Best-case runtime for linear search if key isn't present in the array [Ans: O(n)]</li>
  </ol>
  
  <p>What is the reason that when the key is present in the array, the complexity will reduce to O(1)? Thank you very much!</p>