Time complexity for a small code

Question

I'm trying to find the time complexity for the following code.

N= number of elements in array D= a constant: D>1 V= a constant: V>1000 counter=1; //the maximum value of the counter is N/D. for(i=0; i<N; i++) { [OP1] O1_Operation; // O(1) operation. [Total: N times] [OP2] if(i%D!=0) continue; // O(1) operation. [Total: N times] [OP3] for(j=0;j<counter;j++) // [Total: {(N/D)*((N/D)+1)}/2 times] [OP4] for(s=0;s<V;s++) [OP5] O1_Operation; // O(1) operation. [Total: (V*{(N/D)*((N/D)+1)}/2) times] [OP6] counter++; // O(1) operation. [Total: N/D times] } 

I added each operation time complexity and the total times it will be executed. The confusion for me in this code is because of the mod operation. This mod will allow only (N/D) operations to complete the code OP[3-6].

For [OP3] in the first time it will get execute 1 time, the second 2 times, ..., N/D times. Hence, the total number of executions can be [(N/D) * ( (N/D)+1)] /2. Removing D and V because they are constants will lead to a complexity of O(N^2) for the whole code.

Is this correct?

Answer 1

Yes, you are correct.

Note that some of the choices in complexity analysis are subjective. In your case, N is the number of elements in the array and V is a constant greater than 1000. You chose to present the complexity as O(N²), which is correct as long as V is truly a constant.

However, if the arrays are all fairly limited in size (N < 10²), D is small (2) and V is quite large (> 10⁹), albeit the complexity O(N²) still perfectly describes how your algorithm scales as the input arrays get larger, it doesn't even hint at how long a single iteration takes. As this is being asked in the Software Engineering Stack Exchange, I would like to point out that oftentimes a relationship between the input size and the duration of a computation tells too little to the caller about how expensive a function call actually is.

As a suggestion for your next attempts at analyzing the complexity of a piece of code, performing loop fission can simplify loops such as the one you asked about. For instance, only OP 1 actually needs a loop with N iterations. The rest could only be done for multiples of D, as shown below. This would also remove the expensive integer modulo operator, which can take a noticeable number of CPU cycles in most architectures.

for (i = 0; i < N; i++) { // OP 1 } for (i = 0; i < N; i += D) { // OPs 3 to 6 } 

Answer 2

You are asking on softwareengineering.

You profile your code (measure how long it takes). If it takes too long, making your software less usable, then you improve the code.