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

Question

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

Я знаю, что он должен быть больше O (n) из-за первого цикла.

Но что происходит с временной сложностью после цикла while?

Это O (n) (n-1) = O (n^2 + n)?

int fnA(int n) { 
    int sum=0; 
    for (int i=0; i<n; i++) { 
     int j=i; 
     int product =1; 
     while (j>1) { 
      product ∗= j ; 
      j = j/2; 
     } 
     sum += product; 
    } 
    return sum; 
} 

Answer 1

Это выглядит как O(n log n) для меня. Основная петля выполняет итерацию n раз, и каждая итерация принимает log n дополнительные итерации для завершения, так как j начинается с i и сокращается наполовину до j <= 1. Если вы представляете общее время для всех итераций внутреннего цикла, вы получаете следующую сумму.

O(0 log n) + O(1 log(n-1)) + ... + O(n/2 log (n/2)) + ... + O((n-2) log 2) + O((n-1) log 1) = 
O(log n) + O(n log n) + O(n) = 
O(n log n)