CODEWITHSUNDEEP
cstringtime-complexitybig-ocomplexity-theory
sam0101
sam0101

Reputation: 375

Time complexity of this function /including array of strings

Why is the time complexity of this function O((n^2)*L)(L- the length of maximum string) and not O(n^2)? It seems that strcmp is playing something here but don't know what.

void lex_sort(char *str_arr[]){
 int size = 0, i, j;
 while (str_arr[size] != NULL)
   size++;
 for (i = 0; i < size - 1; i++) {
   for (j = i + 1; j < size; j++) {
    if (strcmp(str_arr[i], str_arr[j]) > 0) {
    // str_arr[i] is greater than str_arr[j]
     char *temp = str_arr[i];
     str_arr[i] = str_arr[j];
     str_arr[j] = temp;
    }
   }
  }
 }

Upvotes: 0

Views: 181

Answers (1)

Bobby Durrett
Bobby Durrett

Reputation: 1303

Looks like n = size which is the number of strings in the array. You have two loops and that makes it O(n^2). But the comparison of strings is O(L). So, you get O(n^2*L). I think you already figured it out. The strcmp is O(L).

Bobby

Upvotes: 1

Related Questions