Как решить одну сложность l oop, когда условие зависит от какой-то другой переменной?

Question

Какова временная сложность для этого кода:

    int p=0;
    for(int i=1;p<=n;i+=2) p=p+i;

Я знаю временную сложность для приведенного выше кода, если i увеличить на 1, тогда временная сложность будет примерно равна √n.

when i=1 -> p=0+1
i=2 -> p=1+2
i=3 -> p=1+2+3
i=4 -> p=1+2+3+4
i=k -> p=1+2+3+4+.....k

Поскольку l oop не зависит от i , то есть не будет n раз. Когда p станет больше, чем l oop будет прервано, следовательно:

p>n
Since p=k(k+1)/2
k(k+1)/2>n
This expression can be written as
k^2=n (approximate)
k=√n

Пожалуйста, помогите мне понять сложность вышеприведенного кода, когда i увеличивается на 2.

Answer 1

Вы можете сделать то же, что и раньше:

i=1 -> p=0+1
i=2 -> p=0+1+3
i=3 -> p=0+1+3+5
...

Таким образом, вы складываете все нечетные числа. Это примерно (в зависимости от того, есть ли у вас нечетное или четное n) n^2/4

Итак, вы ищите k st k^2/4 > n. Так как вы увеличиваете i на два в каждой итерации, k равно двукратному числу итераций, но для записи с большими O это на самом деле не имеет значения, поэтому вы снова получаете O(√n).