1
$\begingroup$
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.

$\endgroup$
4
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Nathaniel
    Commented Mar 18, 2021 at 9:35
  • $\begingroup$ hmmm. Interesting. What if print is outside the inner for loop? What is the time complexity then? $\endgroup$
    – Jonathen
    Commented Mar 18, 2021 at 9:41
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Commented Mar 18, 2021 at 9:52
  • $\begingroup$ 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. $\endgroup$
    – JimN
    Commented Apr 25, 2023 at 23:43

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.