Найти сложность циклов

Question

Мне дан этот алгоритм, и мне сказали найти сложность его большой тета.

for (i = 1; i <= n; i++) { 
    j = n; 
    while(j >= 1) { 
     j = j/3; 
    } 

} 

Я знаю, что наружный для циклов работает n раз. Хотя цикл while более сложный, возможно, это log n (базы 3). В целом, это n * log n

Это правильно?

Answer 1

Существует внешняя петля размера n. Это осложняет фактор n по всей сложности.

Предположим, что внутренний цикл while работает в течение нескольких раз. После i-й итерации значение j будет n/(3^i). Мы будем работать это до п/(3^I)> 1. Таким образом,

=> n/(3^i) = m 
=> n = 3^m 
=> log(n) = log2(3) * m 
=> m = O(log(n)) 

Таким образом, цикл способствует O (N) и в то время как цикл способствует O (журнал (п)). Сложность вложенного цикла становится O (n log (n)).