если условие в сложности O (n * log (n))

Question

s=0

for(i=1; i<n; i = i*2){ 
  if (i<20)
    for (j=0; j<n; j++)
    {
        s=s+i*j;
    }
    s=s+1
}

Я пытаюсь установить сложность биг-о для вышеуказанного алгоритма.Внешний цикл начинается с 1 и продолжается до n , счетчик в i удваивается для каждой итерации, таким образом, это log (n) поведение.Внутренний цикл работает независимо от 0 до n с O (n) поведением .?

Я не понимаю, как если оператор влияет на сложность.Возможно, вы не захотите дать мне ответ, но, пожалуйста, направьте его в правильном направлении, поскольку я его совсем не понимаю.

Answer 1

Внутренний цикл равен O(N), но он будет выполняться только 5 раз, то есть когда i = 1, 2, 4, 8, 16

После первых 5 итераций ваш код в основном становится

for(i=32; i<n; i = i*2){ 
    s=s+1
}

, чтоO(log(N))

Таким образом, общая сложность составляет:

O(5 * N + log(N)) = O(N)