Какова сложность выполнения этого кода во время выполнения?

Question

Какова сложность выполнения этого кода во время выполнения?

#include <cstdio> 
#include <cstring> 
int main() 
{ 
    int n, i, l, j, c, ans = 25; 
    scanf("%d", &n); 
    char x[21], y[21]; 
    scanf("%s", &x); 
    l = strlen(x); 
    for(i=1; i<n; i++) 
    { 
     scanf("%s", &y); 
     c = 0; 
     for(j=0 ;j<l; j++) 
      if(x[j] == y[j]) 
       c++; 
      else 
       break; 
     strcpy(x, y); 
     if(ans > c) 
      ans = c; 
    } 
    printf("%d", ans); 
    return 0; 
} 

Мой преподаватель говорит мне, что сложность этого кода O(n*n) но я не убедил этот ответ вызвать внутренний цикл выполняется раз длиной строки.

Answer 1

Времени выполнения main() состоит из выполнения некоторых утверждений постоянного времени и среды исполнения i -loop:

T_main(n, l) ∈ O(1) + T_fori(n, l) 

i -loop работает точно (n - 1) раз и состоит из некоторых далее константы утверждения времени и времени выполнения j -loop:

T_fori(n, l) ∈ (n - 1) * (O(1) + T_forj(n, l)) 

среда выполнения от J-цикла зависит от данных. В лучшем случае, первый символ x и y различны, таким образом:

T_forj_best(n, l) ∈ 1 * O(1) 

В худшем случае, x и y имеют l равные первые символы, таким образом:

T_forj_worst(n, l) ∈ l * O(1) = O(l) 

Это дает:

T_fori_best(n, l) ∈ (n - 1) * (O(1) + O(1)) = O(n) 
T_fori_worst(n, l) ∈ (n - 1) * (O(1) + O(l)) = O(n * l) 

и

T_main_best(n, l) ∈ O(1) + O(n)  = O(n) 
T_main_worst(n, l) ∈ O(1) + O(n * l) = O(n * l)