Сложность времени - чрезмерные операции?

Question

Возможно ли, что я полностью переоцениваю сложность операции, когда я должен считать только ее? Это вопрос заданий, который у меня есть из моего класса.

Algorithm Power(n) 
Pre: n :: Integer, n > 0 
i = 1 
while (i < n) 
    print i 
    i = i * 3 
done 

Я полностью уверен в себе и думать, что я над мыслящих вопрос

временная сложность O (N) перед упрощением будет O (п) = 1 + (3n +? + 1) Количество раз, когда i = i * 3 выполняется один раз за цикл, но переменная «i» растет с ускорением на каждой итерации, действительно ли это имеет значение, или я слишком много размышляю над вещами?

Это O (n), потому что это всего лишь одна петля или более сложная, чем это, и что-то вдоль линий O (log n) или O (n^(1/3)) из-за ускорения «i»?

Answer 1

Вы правы, что это не O(n). Один уровень цикла соответствует O(n) только тогда, когда счетчик цикла (в этом случае i) линейно увеличивается относительно n. Что касается O(log n) или O(n^(1/3)), я оставлю это вам, чтобы выяснить, так как это для задания.