# Time complexity for a small code

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?

• Does this answer your question? What is O(...) and how do I calculate it? Commented Jun 4, 2020 at 5:50
• Your analysis is correct. If you get 10 times as many elements in the array, then the running time increases with a factor 10*10, thus it is O(N^2). Commented Jun 4, 2020 at 7:26

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(N2), which is correct as long as V is truly a constant.

However, if the arrays are all fairly limited in size (N < 102), D is small (2) and V is quite large (> 109), albeit the complexity O(N2) 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
}
``````