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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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