анализ времени выполнения (сложность времени)

Question

for(i=0; i<n; i++) {
    if(i == x) {
        for(j=0; j<x; j++) {
            x++;
        }
        x *= 2;
    }
}

Что такое анализ времени выполнения для этого цикла?

Answer 1

В цикле

for(j=0; j<x; j++) {
    x++;
}

j всегда будет меньше x, если x начинается больше нуля.Это потому, что вы увеличиваете x каждый раз, когда увеличиваете j.В языке с целочисленной арифметикой произвольной точности это будет выполняться до тех пор, пока у вас не закончатся ресурсы.На языке, подобном C, это приводит к неопределенному поведению.Компилятор может оптимизировать j<x, чтобы всегда быть true, или он мог бы позволить x переполниться до неопределенного (но, вероятно, дополнения до двух) результата.