сложность Big-O в цикле

Question

Если у вас был алгоритм с циклом, который выполнял n шагов в первый раз, то n - 2 второй раз, n - 4 в следующий раз и продолжал повторяться до последнего раза через цикл он выполнил 2 шага, какова была бы мера сложности этого цикла?

Я считаю, что это показывает сложность O (n^2), поскольку число шагов, которые не выполняются, увеличивается квадратично. Мне трудно представить себе такую ​​петлю, которая делает меня менее уверенным в моем ответе.

Любой вид помощи/второе мнение очень ценится :)

Answer 1

Вы правильно, что сложность Θ (п). Это происходит потому, что вы описали это arithmetic progression:

(п - 2) + (п - 4) + ... + 2 (или нечетное число в конце)

(который, очевидно, 2 + 4 + 6 + ... + (n - 2) или эквивалент нечетного начала, BTW).

Использование formula for the sum, это среднее значение первого и последнего элементов, умноженное на количество элементов. Каждое из этих условий составляет Θ (n), а их продукт Θ (n).