Почему сложность времени O (n ^ 2) в этом коде?

Question

Я просто не понял, почему сложность времени O (n ^ 2) вместо O (n * logn)? Второй цикл увеличивается на 2 каждый раз, не правда ли, O (logn)?

void f3(int n){
  int i,j,s=100;
  int* ar = (int*)malloc(s*sizeof(int));

  for(i=0; i<n; i++){
    s=0;
    for(j=0; j<n; j+=2){
      s+=j;
      printf("%d\n", s);
  }
  free(ar);
}

Answer 1

Внешний цикл будет выполняться n раз, и для каждой итерации внешнего цикла внутренний цикл будет выполняться n / 2 раза, потому что j + = 2

Порядок = n × n / 2 = n ^ 2/2 = O (n ^ 2), потому что константа не влияет на время выполнения для больших n

Answer 2

с шагом 2, поэтому цикл будет выполняться для n / 2. Так что сложность будет n * n / 2. если приращение произошло в GP как 2

Answer 3

Увеличивая на два, а не на один, вы делаете следующее N*N*(1/2). С большой (O) нотацией вы не заботитесь о константе, поэтому она все равно N * N. Это связано с тем, что большие (O) обозначения указывают на сложность роста алгоритма.