Что такое среда выполнения этого псевдокода

Question

i = 1; 
while (i <= n) 
    j = i; 
    x = x+A[i]; 
    while (j > 0) 
    y = x/(2*j); 
    j = j/2; // Assume here that this returns the floor of the quotient 
    i = 2*i; 
return y; 

Я не уверен, что мой ответ, я получил O (п).

Answer 1

Позволяет удалить переменные x и y, поскольку это не влияет на сложность.

i = 1; 
while (i <= n) 
    j = i;  
    while (j > 0) 
     j = j/2; 
    i = 2*i; 

1. Во внутреннем цикле вы каждый раз, когда делят j на 2, так что на самом деле это не Liner это O(logn). Например, если j - 16, вы сделаете 5 (O(log16)+1) шагов: 8,4,2,1,0.
2. Во внешнем цикле вы каждый раз умножаете i на 2, так что это также O(logn).

Таким образом, общая сложность будет O(logn * logn).