CODEWITHSUNDEEP
algorithmoptimizationcomplexity-theorybig-operformance
LAC
LAC

Reputation: 1

How to calculate Big-O Notation on the following code

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.

Upvotes: 0

Views: 3190

Answers (3)

67vette427
67vette427

Reputation: 71

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

Upvotes: 0

I GIVE CRAP ANSWERS
I GIVE CRAP ANSWERS

Reputation: 18869

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.

Upvotes: 3

SimonJ
SimonJ

Reputation: 21306

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.

Upvotes: 3

Related Questions