title: Computational complexity of recursion in prolog
body: <p>I've got a recursion:</p>
  
  <pre><code>list_to_set([],[]).
  
  list_to_set([A|X],[A|Y]):-
     list_to_set(X,Y),
      \+member(A,Y).
  
  list_to_set([A|X],Y):-
     list_to_set(X,Y),
     member(A,Y).
  </code></pre>
  
  <p>It converts list of elements into a set. For example [1,1,2,3] -> [1,2,3]. When I enter the query <code>list_to_set([1,1,2,3],X).</code> the result is <code>X = (1,2,3)</code> and the complexity of finding out the set is <code>O(n)</code>. Now I can type <code>;</code> alternative to make sure, that there is no other possible answer. Obviously there is none and script will return <code>false</code>. My question is: what is the computational complexity of that second script run, and why?</p>