title: How to calculate Big-O Notation on the following code
body: <p>I've read the topic:</p>
  
  <p><a href="https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it">Big O, how do you calculate/approximate it?</a></p>
  
  <p>And am not sure what the Big-O notation for the following function would be:</p>
  
  <pre><code>static int build_nspaces_pattern(const char * const value, char *pattern,
          size_t sz_pattern) {
     static char    val_buffer[1025];
     char           *ptr, *saveptr;
     size_t         szptrn;
     ptrdiff_t      offset;
  
     val_buffer[0] = '\0';
     strncat(val_buffer, value, sizeof(val_buffer) - 1);
     val_buffer[sizeof(val_buffer) - 1] = '\0';
  
     pattern[0] = '^'; pattern[1] = '('; pattern[2] = '\0';
  
     for ( ptr=strtok_r(val_buffer, ",", &amp;saveptr);
           ptr!=NULL;
           ptr=strtok_r(NULL, ",", &amp;saveptr)
         ) {
        szptrn = sz_pattern - strlen(pattern) - 1;
  
        if ( sanitize(ptr) != 0 ) {
           return -1;
        }
        strncat(pattern, ptr, szptrn);
        szptrn -= strlen(ptr);
        strncat(pattern, "|", szptrn);
     }     
  
     offset = strlen(pattern);
     pattern[offset-1] = ')'; pattern[offset] = '$'; pattern[offset+1] = '\0';
  
     return 0;
  }
  </code></pre>
  
  <p>Sanitize is O(n), but the for loop will run k times (k is the number of commas in the string).</p>
  
  <p>So, k * O(n) is still O(n), would it be O(n^2), O(k.n) or something else?</p>
  
  <p>Thanks.</p>