Big O

@Ivashenko O · Регистрация: 18.01.2018

Не могу понять как оценить верхнюю границу у этого алгоритма(с++)
n - какое то натуральное число, определенное где-то выше в коде

C++

int sum = 0; 
int i = 1; 
while (sum <= n) { 
    sum = sum + i; 
    i++; 
}

@Shamil1 · 07.03.2018, 09:03

sum_k = k(k+1)/2
Видимо O(sqrt(n))

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,474
	07.03.2018, 09:03	2
	sum_k = k(k+1)/2 Видимо O(sqrt(n)) 0