0
$\begingroup$

First of all, I know there are many questions like this on the site. But I think this case is a bit different.

Consider the following code:

int i, j, k;
for (i = 1; i <= n; i++){ 
 for (j = 1; j <= (n-i); j++) {
 System.out.print(" ");
 }
 for (k = 1; k <= (i-j); k++) {
 System.out.print(i);
 }
 System.out.println();
}

What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.

How our professor told us to compute complexity is just by adding all the summations together from every line.

$$ (n+1) + \sum_{j=1}^{N-i} + \sum_{j=1}^{N-i} + \sum_{k=1}^{i-j} + \sum_{k=1}^{i-j} + n $$

However, I've never seen examples with summations like $\sum_{j=1}^{N-i}$, It's always either $\sum_{j=1}^{N-1}$ or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)?

Raphael
73.3k31 gold badges183 silver badges403 bronze badges
asked Mar 9, 2019 at 11:45
$\endgroup$
5
  • 1
    $\begingroup$ There are two parts here. 1) Derive the correct sums. "Adding all the summations together" is vague; nested loops lead to nested sums. See here. What you wrote down there doesn't make much sense; what's $\sum + \sum$? How do you get four sums from three loops? 2) Simplify the sums. They are particularly easy here, especially with a formulary at hand (e.g. the TCS Cheat Sheet). For help on simplifying sums, please hit Mathematics. $\endgroup$ Commented Mar 9, 2019 at 12:45
  • 1
    $\begingroup$ Community votes, please: Seems like a duplicate of our reference question to me. $\endgroup$ Commented Mar 9, 2019 at 12:47
  • $\begingroup$ Hint for the sums: Sometimes reversing the order of summation can lead to an easily recognized form. $\endgroup$ Commented Mar 9, 2019 at 12:47
  • $\begingroup$ Are you sure that your professor wrote this ? $\endgroup$ Commented Sep 7, 2022 at 10:10
  • $\begingroup$ I suspect that you also incorrectly copied the code, because the presence of j in the third for loop is unexpected. $\endgroup$ Commented Sep 7, 2022 at 10:12

3 Answers 3

0
$\begingroup$

The number of print statements executed is $$ \sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i+1)} 1\right) + 1 \right], $$ where the second sum is zero if 1ドル > i-(n-i+1)$.

The running time is proportional to the number of print statements, so it remains to compute the value of the expression above, or at least to give a good estimate. This I leave to you.

answered Mar 9, 2019 at 13:28
$\endgroup$
3
  • $\begingroup$ When I submitted the assignment, I got a equation very close to your equation there, Exactly, It was $\sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i)} 1\right)\right]$ and I solved it to $n(n+1)/2$ Which seems perfect to me but I still got 3/10 on it. $\endgroup$ Commented Mar 9, 2019 at 13:57
  • $\begingroup$ What he wants is a "line by line analysis" which I don't really understand how to perform. That's why the confused/non-sensical equation in the question. The most ridiculous thing was when he tried to explain that the second inner loop never runs, given any value of n, i, or j afterwards in the class. $\endgroup$ Commented Mar 9, 2019 at 14:00
  • $\begingroup$ You'll have to ask your professor for what he means by "line by line analysis". As for your solution, I'm not 100% sure it's correct, though the expression is certainly $\Theta(n^2)$. $\endgroup$ Commented Mar 9, 2019 at 14:22
0
$\begingroup$

For better analysis the code, you can rewrite loop that use variable $k$ in terms of $n,i$ not $j$:

 int i, j, k;
 
 for (i = 1; i <= n; i++){ 
 for (j = 1; j <= (n-i); j++) {
 System.out.print(" ");
 }
 
 for (k = 1; k <= (i-(n-i+1)); k++) {
 System.out.print(i);
 }
 
 System.out.println();
 }

Let $T(n)$ be time complexity of code. Therefore our code have two disjoint inner loop that displayed by the following summation (suppose each operation System.out.print need constant time, notice that, the inner loop with variable $j$ has the cost $(n-1)+(n-2)+\dots+1=\sum_{i=1}^{n-1}i$), so:

$$T(n)=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}\left(\sum_{k=1}^{i-n+i-1}\mathcal{O}(1)\right)$$ $$=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}\left(\sum_{k=1}^{2i-n-1}\mathcal{O}(1)\right)$$ $$=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}(2i-n-1)=\Theta(n^2)+\mathcal{O}(n^2)$$ $$=\Theta(n^2)$$

answered Jul 26, 2021 at 19:23
$\endgroup$
0
$\begingroup$

Let us work out an example with $n=5$.

The outer loop is executed with $i=1,2,3,4,5$. Thus the first inner loop executes 4ドル+3+2+1+0$ print's. And the second inner loop 0ドル+0+0+2+4$ print's.

For $n=6$, we have 5ドル+4+3+2+1+0$ print's. And the second inner loop 0ドル+0+0+1+3+5$ print's.

We can easily generalize and get the counts $n$ (outer), $\dfrac{(n-1)n}2$ (first inner) and $\dfrac{n^2-1}4$ or $\dfrac{n^2}4$ depending on the parity of $n$ (second inner).

answered Jan 5, 2023 at 20:19
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.