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

Question

Вычислить временную сложность этого фрагмента кода, если функция «процесс» имеет сложность O (LogN)

void funct (int a[], int n) 
{ 
    int i=0 
     while (i < n){ 
     process (a, n); 
     if (a[i]%2 == 0) 
      i = i*2+1; 
     else 
      i = i+1; 
    } 

Я пытался вычислить наилучший и наихудший случай сложности времени;

Худший случай, когда «еще» заявление дозвонилось таким образом это должно быть просто:

В худшем случае: Т (п) = O (NlogN)

У меня есть некоторые проблемы с лучшим случаем. Я попробовал этот путь, но я не знаю, если это правильно

Так как в «если» заявление «я» получить приращение на «2i + 1» должно быть

i=2^k-1 
2^k < n+1 

so k < log_2(n+1) 

Является ли правильным сказать, что цикл while выполняется (log_2(n+1)-2)/2 раз, потому что это последнее возможное значение, для которого i < n?

Если это так, то сложность времени O (lognlogn) в лучшем случае?

Answer 1

Наилучший случай, если выборковые значения в a все четные. В этом случае сложность составляет O(log(n)*log(n)), так как счетчик циклов составляет O(log(n)).

В худшем случае, если выбранные значения в a являются нечетными. В этом случае сложность составляет O(n*log(n)), так как счетчик циклов составляет O(n).