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

Question

Ниже приведен фрагмент кода, содержащий вложенный l oop. Технически это должно быть

O(variableFour*variableFour),

, но это не так.

void main() { 
   int variableOne, variableTwo, variableThree = 0;
   int variableFour = 10;

   for (variableOne = variableFour / 2; variableOne <= variableFour; variableOne++) {
      for (variableTwo = 2; variableTwo <= variableFour; variableTwo =variableTwo * 2) {
         variableThree = variableThree + variableFour / 2;
      }
   }
}  

Answer 1

Это не O(variableFour * variableFour) == O(variableFour**2). Посмотрите на внутренний l oop:

 for (variableTwo = 2; variableTwo <= variableFour; variableTwo = variableTwo * 2)

Обратите внимание, что мы умножаем , а не складываем: variableTwo = variableTwo * 2, поэтому мы l oop больше

 variableTwo = 2, 4, 8, 16, ..., 2**i, ..., variableFour

Таким образом, внутренняя l oop сложность равна O(log(variableFour)), а комбинированная сложность (как для внутреннего, так и для внешнего цикла) составляет

 O(variableFour * log(variableFour))