Пример сложности алгоритма времени

Question

Я недавно понял нотацию Big Oh. Недавно я столкнулся с примером, приведенным в книге.

void Function(int n) 
{ 
int i=1 ; 
int s=1 ; 
while(s <= n) 
{ 
i++ ; 
s= s+i ; 
print(\*"); 
} 
} 

Я не знаю, каким образом автор приходит к временной сложности алгоритма выше, как O (√n). Я просто хочу понять процесс достижения такого вывода?

Answer 1

Его можно легко увидеть как s is growing quadratic in terms of number of iteration.

s = 1 // set as 1 initially Теперь мы добавляем S = s + i // Where i increasing linearly by one unit in each iteration

//So it's just a addition i.e. s = 1 + 2 + 3 +4 ....+i, which will sum up to s = i(i+1)/2 Поэтому s = i(i+1)/2 = (i^2+i)/2 где я есть число итераций.

Теперь в i итерации мы получаем s = (i^2+i)/2 Чтобы получить s >=n мы требовали только √n итераций. Следовательно, временная сложность данной программы будет O(√n).