title: Best algorithm for delete duplicates in array of strings
body: <p>Today at school the teacher asked us to implement a duplicate-deletion algorithm. It's not that difficult, and everyone came up with the following solution (pseudocode):</p>
  
  <pre><code>for i from 1 to n - 1
      for j from i + 1 to n
          if v[i] == v[j] then remove(v, v[j])    // remove(from, what)
      next j
  next i
  </code></pre>
  
  <p>The computational complexity for this algo is <code>n(n-1)/2</code>.  (We're in high school, and we haven't talked about big-O, but it seems to be <code>O(n^2)</code>).  This solution appears ugly and, of course, slow, so I tried to code something faster:</p>
  
  <pre><code>procedure binarySearch(vector, element, *position)
      // this procedure searches for element in vector, returning
      // true if found, false otherwise. *position will contain the
      // element's place (where it is or where it should be)
  end procedure
  
  ----
  
  // same type as v
  vS = new array[n]
  
  for i from 1 to n - 1
      if binarySearch(vS, v[i], &amp;p) = true then
          remove(v, v[i])
      else
          add(vS, v[i], p)      // adds v[i] in position p of array vS
      end if
  next i
  </code></pre>
  
  <p>This way <code>vS</code> will contain all the elements we've already passed. If element <code>v[i]</code> is in this array, then it is a duplicate and is removed. The computational complexity for the binary search is <code>log(n)</code> and for the main loop (second snippet) is <code>n</code>. Therefore the whole CC is <code>n*log(n)</code> if I'm not mistaken.</p>
  
  <p>Then I had another idea about using a binary tree, but I can't put it down.<br>
  Basically my questions are:</p>
  
  <ul>
  <li> Is my CC calculation right? (and, if not, why?)</li>
  <li> Is there a faster method for this?</li>  
  </ul>
  
  <p>Thanks</p>