What is the runtime of this pseudo-code

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;

I'm not sure about my answer, I got O(n²).

Answer 1

Lets remove x and y variables because it doesn't affect to complexity.

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

1. In the inner loop you every time divide j by 2, so actually it is not liner it is O(logn). For example when j is 16 you will do 5 ( O(log16)+1 ) steps: 8,4,2,1,0.
2. In the outer loop you every time multiply i by 2, so it is also O(logn).

So overall complexity will be O(logn * logn).