How to find time complexty of algorithm

Question

I'm supposed to find the time complexity of this algorithm but I'm not sure I fully understand how to go about this. Could anyone help explain to me how to find the big-tome complexity, in big-O notation, for this algorithm?

given an array A[1,...,n] of integers

i := 1;
x := 0;
while(i <= n)
    j := 1;
    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;

What I am asking for is an explanation on how to approach a problem like this one.

Answer 1

As j is always set to 1 before the inner loop starts, and then gets to be 0 at the integer division, that inner loop will always run exactly one time. As a consequence the code can be seen like this, eliminating the operations on variable j, which do not affect the overall time complexity:

i := 1;
x := 0;
while(i <= n)
    x := x+A[i];
    y := x/2;
    i = 2*i;
return y;

As i will go through the sequence of powers of 2, the remaining loop will iterate 1+floor(log(n)) times.

Assuming that the arithmetic operations execute in constant time, the time complexity is O(log n).