Какое время работы цикла увеличивается экспоненциально с определенным компаратором?

Question

Каково время работы в Big-O этого цикла:

for(int n=100; n <= 60000; n = n * 3){
....inner loop code....
}

Я думаю, что это O (logn), но я не уверен, потому что он выполняется определенное количество раз.Начиная с 100 и заканчивая 60000, умножая на 3 каждый раз, мы устанавливаем определенное количество раз.Это O (logn)?

Answer 1

Сложность равна O (log3 n), предполагая, что код внутри цикла равен O (1)

Поскольку вы умножаете на 3 каждую итерацию, количество повторений будет примерно равно x где 100 * 3 ^ x = 60000.

Чтобы изменить формулу в терминах x, вы получите 3^x = 600, поэтому x = log3(600).

Теперь я предполагаю, что 60000 - это вводn здесь, и вы хотите узнать, как изменяется необходимое время, когда вы увеличиваете это число, вы получаете отношение log3.

Answer 2

Правильный ответ O (1), потому что цикл выполняется определенное количество раз, в этом случае его всегда линейное время.

Answer 3

Это не O (log n).Как вы говорите, время выполнения этого цикла является постоянным и не зависит от некоторой переменной n.Здесь вы бы использовали нотацию Big-O, если число раз, которое выполняется цикл, зависит от некоторого параметра, который был предоставлен извне (например, длина массива или что-то, что обрабатывает этот алгоритм)