# Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)}

for(int i = 1;i<=n;i++){
for(int j = i+1;j<=n-i;j++){
print("hello");
}
}


The first loop has time complexity of n and second for loop is dependent on i. That means for every i, the number of time inner for loop gets executed is: $$\sum_{k=1}^{n/2}(n-2k)$$ After doing some algebra, I get: $$\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2}$$. This is the time complexity for inner for loop. Now we multiplying outer loop $$n*(\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2})$$. Therefore, time complexity is $$\Theta (n^3)$$. But this can't be right? It should max be $$\Theta n^2$$. Cause inner loop doesnt get executed for every i value.$$\forall i \; \; \;i>n/2$$ inner loop doesnt get executed at all.

• The sum $\sum\limits_{k=1}^{n/2}(n-2k)$ is already the total number of print done by your execution, not the number of times the inner loop gets executed. So the complexity is indead $\Theta(n^2)$. Commented Mar 18, 2021 at 9:35
• hmmm. Interesting. What if print is outside the inner for loop? What is the time complexity then? Commented Mar 18, 2021 at 9:41
• If you mean for i … {print("hello"); for j… {}}, then the time complexity stays the same (there are $n$ total print, but the inner loop is still executed). Commented Mar 18, 2021 at 9:52
• If you applied your logic to nested for loops i=1..n and j=1..n you would again get $\Theta(n^3)$. So you need to pay attention to your flawed argument.
– JimN
Commented Apr 25, 2023 at 23:43

Suppose $$i=1$$ then inner loop get executed $$n-2$$ times because of $$2\leq j\leq n-1$$ and $$j$$increment each step by one, As a result $$n-1-2+1=n-2$$ times inner loop executed.

If $$i=2$$ then inner loop executed $$n-4$$ times ... until $$i=\frac{n}{2}$$ inner loop executed 1 time.

Value of $$i$$ #inner loop executed
$$i=1$$ $$n-2$$
$$i=2$$ $$n-4$$
$$i=3$$ $$n-6$$
... ...
$$i=\frac{n}{2}$$ $$n-(n-1)$$

It's equal to following summation:

$$\frac{n}{2}\times n-2\sum_{i=1}^{\frac{n}{2}}i=\frac{n^2}{2}-\frac{n\times(\frac{n}{2}+1)}{2}=O(n^2)$$

If you want to calculate time complexity using asymptotic notation, it's even easier (that's why it's so useful!).

In the first for loop

for(int i = 1 ; i <= n ; i++)


the number of iterations increases linearly with the size of the input ($$n$$).

The second,

for(int j = i + 1; j <= n - i; j++)


the number of iterations is also linear in $$n$$. In this case the iterations are not exactly $$n$$ (in fact they are $$(n - i) - (i + 1) + 1$$), but it is still linear in $$n$$ (even though the range is affected by $$i$$).

Clearly if you need the exact number of operations, you have to take into account the $$i$$ in the second for.

If you want to just calculate the complexity using asymptotic notation, you should just identify that you have 2 nested for loops that each is lineal in $$n$$:

$$\text{So the complexity is } \Theta(n^²)$$

furthermore, if is $$\Theta(n^2)$$, it is also $$O(n^2)$$

Consider the following code and equivalently transformed versions:

count= 0;
for(int i = 1; i<=n; i++) {
for(int j = i+1; j<=n-i; j++) {
count++;
}
}


count= 0;
for(int i = 1; i<=n; i++) {
count+= max(0, n - 2*i);
}


count= sum(1 ≤ 2i ≤ n:n - 2*i)


Using the triangular numbers, for even n=2m the final value of count is

mn - 2m(m+1)/2 = m²-m.


The result is similar for odd n.