O (logn) время выполнения цикла while?

Question

Я видел эти два примера в Интернете и пытаюсь выяснить время выполнения для каждого.У меня есть предположение относительно того, какими могут быть обе среды выполнения, но я не уверен, особенно вторая проблема.

    int temp=0;
    int i=0;
    while(temp < n){
        arr[i]++;
        i++;
        temp = i*i;
    }

Я полагаю, что время выполнения для этого равно O (log n), потому что цикл while выполняется примерно n * 2 раза, что заставляет меня думать, что это так.

int i = 0;
int j = 1;
while (j<n){
    i++;
    if(i==n){
        i = 0;
        j = j*2;
    }
}

Мое лучшее предположение в этом также O (logn).Я действительно не знаю, как думать об этой проблеме.Я знаю, что каждая подзадача (чтобы попасть внутрь оператора if) выполняется n раз.Поэтому время выполнения составляет около O (n * 3) (я думаю) == O (logn).

Answer 1

Первый фрагмент соответствует:

int i=0;
while(i*i < n){
    arr[i]++;
    i++;
}

, который имеет сложность O(sqrt(n)), поскольку i*i < n совпадает с i < sqrt(n).

Для второго

int i = 0;
int j = 1;
while (j<n){
  i++;
  if(i==n){
    i = 0;
    j = j*2;
  }
}

давайте заметим, что j сбрасывается после n шагов к 2*j.Если это произойдет k раз, j станет 2^k.Поскольку предел равен n, у нас есть 2^k < n или k < lg(n).В итоге будет lg(n) сброс j, каждый из которых включает n шагов.Следовательно, сложность составляет O(n lg(n)).