Determine the run-time of a pseudo code

Question

I have the following pseudo-code which I want to determine its run-time T(n). Can someone please give me the steps I should follow ? Here is the code:

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;

Answer 1

I think it's O(log log N) if my calculation is not wrong.

First, we omit the lines that does not affect the loop times, also assume array random visit as O(1).

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

Then we assume that all the operations in one line are done in O(1), we add them up and get the result.

Besides the math analysis, we can also use computational: we run the fragment for several times and see the time growth (I also omitted the operations that does not affect the loop times).

#include <iostream>
using namespace std;

int main(){
    long long i, j, n;
    double cost;
    clock_t start, finish;
    i = 1;
    n = 1000000000000;
    start = clock();
    while (i <= n) {
        j = i;
        while (j > 0) {
            j = j / 2;
        }
        i = 2 * i;
    }
    finish = clock();
    cout << (double)(finish - start)/CLOCKS_PER_SEC << endl;
}