Определение асимптотическую сложность в худшем случае (O (N)) конкретной функции

Question

Я хотел бы определить асимптотическую сложность в наихудшем случае следующую функцию:

int j; 
float r = 1.0; 
for (int i=1; i<(log n); i++){ 
    j = 1; 
    while (j <= i^2){ 
     r*=2; 
     j++; 
} 
print(r); 

Answer 1

Во-первых, я буду считать, что i^2 в вашем коде означает «i, увеличенный до 2", а не «i bitwise-XOR 2», поскольку последний соответствует синтаксису C++, но дает непредсказуемые результаты.

сложность времени задается суммой

Нам нужно оценить суммы натуральных чисел к власти 2, используя данные из этой страницы: http://www.trans4mind.com/personal_development/mathematics/series/sumGeneralPowersNaturalNumbers.htm.

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