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

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

• This is not how determining the running time works. Mar 2, 2022 at 15:07

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)$$.

• How could I label the inner using T(n) = ... without making as to be an O(1)? Mar 2, 2022 at 15:13
• Sorry, I don't understand your question. Mar 2, 2022 at 15:14
• for example x = 0; for (int i=0; i<n; i++){ for (int j = i, j < n, j ++) { x = x + 1; } } the running time repetitive is T(n) = k’ + kn/2 + kn^2/2. see link csd.uwo.ca/Courses/CS1027b/notes/AnalysisIntro.pdf Mar 2, 2022 at 15:16
• I'm sorry, I still don't understand the question. Try to use full sentences. Mar 2, 2022 at 15:17
• as for the example above every assigning value will count as 1, so I want to get the T(n) repetitive with exact label of the operation like j = i is n - i. Mar 2, 2022 at 15:20

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).


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$$.

You are looking at shell sort. Shell sort operation count is very, very hard to analyse. There is a very simple outer loop which is iterated log n times, but that is of very little use. There is a second loop, which will get iterated about n log n times, and there is an inner loop.

I’d first check if your code is actually shell sort. I’m not entirely convinced.

In the innermost loop you’d have to analyse how much it matters that the array is partially sorted. Worst case it runs in O(n) when interval = 1 making everything O(n^2) unless the loop exits early.

I’d suggest you first do some experiments, figure out the execution time experimentally, then prove your results.