OPTIMALITY

• Is the sequential search algo. optimal?
• Is there another algo. which solves the same problem using fewer number of comparisons?
• Theorem: In the worst case,
  
  $$W(n)=n$$
  
  

• Proof by contradiction
  
  • If there is another algo B whose $W(n)<n$, then the element not seen by B may be $x$ & $B$ would be incorrect.
    

    ($O(\log n)$ on an ordered list & $O(1)$ in a characteristic vector alternatives only when performing multiple searches.)

  • $\Rightarrow$Lower Bound on the number of comparisons for searching in an unordered list is $n$.