Каково время выполнения следующего кода?

Question

Разве это не просто время n-i, это просто O (n)? Или я не рассматриваю все в этой ситуации?

i <- c 
while i < n do 
i <- i*c 
end while 

Answer 1

Не было бы логарифмом с базой c от n?

Вы в основном умножаете i до тех пор, пока не достигнете значения n.

Answer 2

Время работы этого алгоритма: O (log n). Это не будет n-i, потому что вы не увеличиваете счетчик циклов путем добавления или вычитания значения. Скорее, вы увеличиваете счетчик циклов на c, чтобы вы увеличивали его на c в каждой итерации. Таким образом, максимальное количество итераций, которые он может выполнить, - log_c (n).