Сложность алгоритма с итерациями.Это логарифмическое или экспоненциальное?

Question

Если у меня есть следующий алгоритм

for (i = 1; i <= 4 * n; i = i * 4) {
   for (k = 1; k < 1000; k = 2 * k) {
       print(k);
   }
   print(i);
}

, как я могу рассчитать его сложность?Я только понимаю, что для одной итерации for(i=1; i≤4n; i=i*4) строка с print(i) равна O (1), а для одной итерации for(k=1; k<1000; k=2*k) строка с print(k) равна O (1).

Я не уверен, как поступить.

Answer 1

Вот внутренний цикл:

for(k=1; k<1000; k=2*k) {
    print(k);
}

Этот цикл является постоянным временем, потому что нет свободных переменных.Он всегда будет вызывать print ровно 9 раз, для k ∈ {1,2,4,8,16,32,64,128,256,512}.

Внешний цикл равен O (log n), потому что он будет выполнять ⌊log₄ 4n⌋ раз.

В целомоставленный вами фрагмент программы (если мы добавим последнюю закрывающую скобку, которую вы пропустили) равен O (log n).