algorithm analysis - complex dependant nested loop

Question

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: 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.
• Raphael: Community votes, please: Seems like a duplicate of our reference question to me.
• Raphael: Hint for the sums: Sometimes reversing the order of summation can lead to an easily recognized form.
• user16034: Are you sure that your professor wrote this ?
• user16034: I suspect that you also incorrectly copied the code, because the presence of j in the third for loop is unexpected.

Answer 1

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.

• candh: 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.
• candh: 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.
• Yuval Filmus: 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)$.

Answer 2

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

Answer 3

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