Big-О и тета обозначения конкретной функции ... Продолжительность

Question

Если оценка п (п) тета (п)

i = 1; 
sum = 0; 
while (i <= n) 
     do if (f(i) > k) 
      then sum += f(i); 
      i = 2*i; 

Будет ли время работы этого быть O (N^3), потому что из n раз функции, возможно, называются или будет O (n)? Или это что-то в терминах тета, так как это информация, которую мы знаем? Я очень потерял на этом ...

Answer 1

Переменная двойники я каждый раз => достигнет п в log2 (п) времени. Оценка f будет выполнена Log2 (n) times => Сложность времени функции равна O (N x LogN).

В самом деле, если вычисления F (I) имеет сложность O (I), то время сложность:

1 + 2 + 4 + ... + 2^(Log2(n)) = n (there are Log2(n) steps) => O(n)