title: Alternative O(N^2) time complexity with O(1) space complexity for finding distinct values in array
body: <p>I am trying to see whether there is any alternative to brute force algorithm (or a slight improvement/worst performance to a naive brute force algorithm) that will still result in O(N^2) time complexity and O(1) auxiliary space.</p>
  
  <p>This is my brute force pseudocode:</p>
  
  <pre><code>    procedure distinct(Input: array)                             
          for i=0 to i &lt; length of array                      
              for j=i+1 to j &lt; length of array                 
                 if array[i] == array[j] and i != j then  
                    return false                        
                 end if
                 increment k
              end for
              increment j
          end for
          return true
      end procedure
  </code></pre>
  
  <p>I know that brute force algorithm is a terrible solution and there are many ways of achieving much better performance (using data sets or achieving O(N) time complexity and O(1) space complexity), however out of pure interest I am trying to find the O(N^2) worst case time complexity and O(1) space complexity. Is it even possible?</p>
  
  <p>I was thinking that I could possibly apply a sorting algorithm (e.g. Bubble or Insertion sort), then use a for loop to go through sorted array, but would that still give me a quadratic function and not O(N^3)?</p>