# algorithm analysis - complex dependant nested loop

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

• 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 Mar 9 '19 at 12:45
• Community votes, please: Seems like a duplicate of our reference question to me. – Raphael Mar 9 '19 at 12:47
• Hint for the sums: Sometimes reversing the order of summation can lead to an easily recognized form. – Raphael Mar 9 '19 at 12:47

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)$$.
• 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 Mar 9 '19 at 13:57
• 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)$. – Yuval Filmus Mar 9 '19 at 14:22