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)?
-
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$Raphael– Raphael2019年03月09日 12:45:19 +00:00Commented Mar 9, 2019 at 12:45
-
1$\begingroup$ Community votes, please: Seems like a duplicate of our reference question to me. $\endgroup$Raphael– Raphael2019年03月09日 12:47:06 +00:00Commented 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$Raphael– Raphael2019年03月09日 12:47:54 +00:00Commented Mar 9, 2019 at 12:47
-
$\begingroup$ Are you sure that your professor wrote this ? $\endgroup$user16034– user160342022年09月07日 10:10:26 +00:00Commented 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$user16034– user160342022年09月07日 10:12:37 +00:00Commented Sep 7, 2022 at 10:12
3 Answers 3
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.
-
$\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$candh– candh2019年03月09日 13:57:01 +00:00Commented 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$candh– candh2019年03月09日 14:00:45 +00:00Commented 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$Yuval Filmus– Yuval Filmus2019年03月09日 14:22:46 +00:00Commented Mar 9, 2019 at 14:22
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)$$
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).
Explore related questions
See similar questions with these tags.