Сложность времени следующего кода, который использует 3 вложенных цикла

Question

Может кто-нибудь объяснить правильное время Сложность этого кода ниже.

int sum,i,j,k,n;
sum = 0;
cin>>n;
int arr * = new int[n];
for (i=1;i<n;i=i*2){
   cin>>arr[i];
   for (j=0;j<n;++j)
       for (k=1;k<=n;k=k*2)
           sum+=arr[j];
}

Answer 1

Границы трех циклов for не имеют каких-либо взаимозависимостей. Итак, мы должны быть в состоянии выяснить общее время выполнения, просто умножив сложность трех циклов.

Циклы в i и k равны O(lgN), потому что они удваивают счетчик цикла на каждой итерации. Средняя петля в j равна O(N). Это дает O(N*lgN*lgN) в качестве общей сложности.