Как найти big-O для вложенной l oop, которая имеет как понижающие, так и повышающие значения

Question

Как найти сложность времени для следующего кода?

сумма j от j=n до n/(3^(j-1))

это псевдокод, из которого я получил суммирование.

j=n
while (j>=1)
  for (i=1 to n)
    x=x+1
  j=j/3
}

Answer 1

Это будет O (n log_3 (n)). На самом деле, на каждой итерации вы должны покрывать треть предыдущей длины. Так что n + n / 3 + n / 9 + n / 27 + ...

Answer 2

Если вы предполагаете n = 3^k, число итераций для внешнего l oop будет k = log_3(n). Поскольку у нас есть oop с n итерацией (внутренняя l oop), общая сложность времени будет T(n) = \Theta(n \log_3(n)).

Более того, как log_3(n)/log_2(n) = log_3(2) = constant, мы можем иметь T(n) = \Theta(n log(n)) (log(n) == log_2(n)).