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)$. – Nathaniel Mar 18 at 9:35
• hmmm. Interesting. What if print is outside the inner for loop? What is the time complexity then? – Jonathen Mar 18 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). – Nathaniel Mar 18 at 9:52

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