0

I've read the topic:

Big O, how do you calculate/approximate it?

And am not sure what the Big-O notation for the following function would be:

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, ",", &saveptr);
         ptr!=NULL;
         ptr=strtok_r(NULL, ",", &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;
}

Sanitize is O(n), but the for loop will run k times (k is the number of commas in the string).

So, k * O(n) is still O(n), would it be O(n^2), O(k.n) or something else?

Thanks.

Community
  • 1
  • 1
LAC
  • 1
  • 1
  • 1
  • This question would be easier to answer if you provide a simplified pseudo-code version of your algorithm. – Björn Pollex Nov 10 '10 at 22:09
  • Don't forget to take the string operations into account - they may or may not make a difference in your calculation (eg. strtok, strlen, strncat, etc.) – MahlerFive Nov 10 '10 at 22:12

3 Answers3

3

Looks O(n) to me, at a glance.

  • strtok_r() iterates through the original string = O(n)

  • sanitize() you say is O(n), but this is presumably with respect to the length of the token rather than the length of the original string, so multiply token length by number of tokens = O(n)

  • strncat() ends up copying all of the original string with no overlap = O(n)

  • you append a fixed number of characters to the output string (^, (, ), $ and a couple of NULLs) = O(1)

  • you append a | to the string per token = O(n)

But wait!

  • you call strlen() over the output pattern for every iteration of the loop = O(n^2)

So there's your answer.

SimonJ
  • 21,076
  • 1
  • 35
  • 50
2

One way to approach it I like is to replace code with the running times, so for instance

val_buffer[0] = '\0';
strncat(val_buffer, value, sizeof(val_buffer) - 1);
val_buffer[sizeof(val_buffer) - 1] = '\0';

becomes

O(1)
O(n) (* Assume the size of value is the size of the input *)
O(1)

A loop

for each k in value {
  strlen(value)
}

becomes

O(n) {
  O(n)
}

or something such notation, which you can then make into O(n) * O(n) = O(n^2). You can then sum up all the listed big-oh times to obtain your final time complexity.

A similar trick is to first lace all of your code with counts of how much work is done, then remove the code that does the real work leaving only the counts. Then using simple math to simplify the counts. I.e.,

count = 0;
for (i = 0; i < k; i++) {
    count++
}

is easily seen to be replaceable by count = k.

I GIVE CRAP ANSWERS
  • 18,739
  • 3
  • 42
  • 47
0

Why is everyone assuming strlen = O(n)? I thought O(n) was only for loops.

67vette427
  • 71
  • 1
  • 7
  • Strlen can be thought of as: int strlen(char* s) { int len = 0; while (*s++) len++; return len; } Thus, if N is the length of the string, strlen is O(N) because it IS a loop. – James Dec 10 '10 at 06:32
  • and how do you determine strncat is not a while loop copying 1 byte at a time? Is this the assumption part of big O notation? – 67vette427 Dec 10 '10 at 23:19