title: Is the execution time of this unique string function reduced from the naive O(n^2) approach?
body: <p>The generic algorithm to deduce if a string contains all unique characters (and that does not use any other data structures) says to go through the string, iterating each letter against the entire string searching for a match. This approach is <em>O(n^2)</em>.</p>
  
  <p>The approach below (written in C) uses an offset for the iterating over the string part, since for example in a short string there is no reason to test the last character with the first character as the first character already did that.</p>
  
  <p>My question is this: Is the runtime of the algorithm then <em>O(n!)</em> or something like <em>O(nlogn)</em>?</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  int strunique(const char *str)
  {
      size_t offset = 1;
      char *scout = (char *)str, *start;
  
      for (; *scout != '\0'; ++scout, ++offset)
          for (start = (char *)str + offset; *start != '\0'; ++start)
              if (*start == *scout)
                  return 0;
  
      return 1;
  }
  
  int main(void)
  {
      printf("%d\n", strunique("uniq"));
      printf("%d\n", strunique("repatee"));
  
      return 0;
  }
  </code></pre>