How many times will a function be called?

Question

Here I have a loop:

for (i = n; i < 2*n; i += 4) {
    for (j = 0; j < 3*i; j += 2) {
        function();
    }
}

How can I count the number of calls (in terms of n) of function () without running this code?

As an idea, I think I can use an arithmetic progression, which has the sum S = (a1 + ak) * k / 2, where a1 is the number of iterations of the inner loop, while I have the initial value, ak is the number of iterations of the inner loop , while I have a finite meaning.

But I can not express it as one formula with n as a variable.

Do you have any ideas about this?

Answer 1

The inner loop makes 3 * i / 2 calls. The outer loop has i = n, n + 4, n + 8 .. 2n-4. Therefore, we have:

count = 3*n/2 + 3*(n+4)/2 + 3*(n+8)/2 + ... 3*2*n/2 =
= 3/2 * (n + (n+4) + (n+8) + .. + (2n-4)) = 
= 3/2 * (3n^2-4n) / 8 =
= (9n^2 - 12n) / 16

(Edit: , )

# 2 - self, .

Answer 2

, . = n, 3n/2 ( - ). , , , n 4, . n/4 ( ).

Answer 3

, function():

n + ceil (n/4) - 1 , . .