How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?

Question

I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation so that I can get that exact Running time of this shell short algorithm

for (int interval = n/2; interval > 0; interval /= 2)  
    {  
        for (int i = interval; i < n; i += 1)  
        {  
            /* store a[i] to the variable temp and make the ith position empty */  
            int temp = a[i];  
            int j;        
            for (j = i; j >= interval && a[j - interval] > temp; j -= interval)  
                a[j] = a[j - interval];  
              
            // put temp (the original a[i]) in its correct position  
            a[j] = temp;  
        }  
    }  

               1    (1 or n-1)?
int interval   =     n / 2      

now here with condition that I am referring as i < 0 which is n+1 in other operation sample.

       (n+1)
interval > 0

I know that the operation of this is log base2

         log base 2  
interval /= 2

Answer 1

Rewrite it as follows:

interval = n/2
while (interval > 0) {
    ....
    interval = interval/2
}

Each of the three operations takes $O(1)$. The running time of the loop is the total running time of all iterations. It depends on what happens on each iteration. As an example, consider the code

for (interval = n/2; interval > 0; interval /= 2)
    interval = 0;

This code runs in $O(1)$.

Answer 2

Assuming that the body of the main loop takes f(n) operations, the total operation count will be (for n an exact power of 2)

f(n/2) + f(n/4) + f(n/8) + ... f(2) + f(1).

Answer 3

To analyze the running time of loops, we need to know how many times the loop executes, and then we write the total time as the sum of the time needed for each execution. When a "for" loop is determined by an index that starts at one number, ends at another, and increments once per execution, this is easy, and can be translated directly to summation notation. For the following loop,

for (int i=a; i<=b; i++) {
   perform_1_operation;
}

we can write the number of operations performed as $$ \sum_{i=a}^b O(1) = O(b-a)$$ And for the following nested loop

for (int i=a; i<=b; i++) {
   for (int j=i; j<=b; j++) {
       perform_1_operation;
    }
}

we can write the number of operations performed as $$ \sum_{i=a}^b \sum_{j=0}^i O(1) = \sum_{i=a}^b O(i) = O(b^2-a^2)$$ (Don't worry too much about how I evaluated this if you aren't familiar.) But in your case, the first loop is not so easy. However, we can think about transforming it from

for (int interval = n/2; interval > 0; interval /= 2) {
    ... 
}

to

for (int i=1; i<= log_2(n); i++) {
    interval = n/2^i;
    ... 
}

which can then be analyzed as usual. You should spend some time picking specific values of $n$ and checking that these two loops are indeed the same, and then think about why it is true for any positive integer $n$.