Proof: (Binary search is optimal)

• Numbers of nodes in any decision tree is
  
• Minimum numbers of levels in any binary tree with n nodes is (H.W.)
  
• is a lower bound on problem complexity
  
• Binary Search is optimal