title: Calculating O(n) for a hasmap vs binary search
body: <p>I'm trying to clarify how to calculate O(n) for the following case:</p>
  
  <p>Given a sorted array, how would you find two numbers whose sum is equal to a given number x in O(n)?</p>
  
  <p>An O(n) solution would be:</p>
  
  <ol>
  <li>Remove the first element of the array (e0)</li>
  <li>Add this to a hashmap</li>
  <li>Remove the first element of the array (e1)</li>
  <li>Target is the difference between e1 and x</li>
  <li>If the target exists in the hash map return the pair</li>
  <li>Add e1 to the hashmap</li>
  <li>Repeat steps 3-6 until you find a pair or run out of elements</li>
  </ol>
  
  <p>This would be worst case O(n) as you only need a single pass on the array.</p>
  
  <p>An O(n * log n) solution would be:</p>
  
  <ol>
  <li>Remove the first element from the array (e1)</li>
  <li>Target is the difference between the first element and x</li>
  <li>Binary search the rest of the array for the target </li>
  <li>If it exists return the pair</li>
  <li>Repeat steps 1–4 till you find a pair or run out of elements</li>
  </ol>
  
  <p>This is O(n log n) as you would need to run a binary search (log n) at worst n/2 times giving O(n/2 * log n) which in big O is O(n * log n)</p>
  
  <p>Is this correct?</p>