There is a strong connection between analysis of algorithms and counting. The two main basic ideas in counting is the addition rule and multiplication rule.
In this question, the number of times the println statement is executed depends on the value of j. If j is even, the the inner loop executes n - i times, else it executes j times.
One way to visualize the number of times the println statement is executed is to draw a table,
| i/j | 0 | 1 | 2 | 3 | 4 | … |
|---|---|---|---|---|---|---|
| 0 | n | 1 | n | 3 | n | … |
| 1 | n-1 | 1 | n-1 | 3 | n-1 | … |
| 2 | n-2 | 1 | n-2 | 3 | n-2 | … |
| 3 | n-3 | 1 | n-3 | 3 | n-3 | … |
| 4 | n-4 | 1 | n-4 | 3 | n-4 | … |
| … | ||||||
A standard method to count the number of operation is to convert loops into summations as follows, `\sum_{i=0}^{n} \sum_{j=0}^n \sum_{k=i}^{j} 1`
However, solving the above summation is rather tedious. Observe that we are actually adding up the lengths of the segments, therefore it does not matter where the segments start and end. Hence, another way to count the number of operations is to do so according to the lengths, which gives us the following expression, `\sum_{l=1}^n (n - l + 1)l`.
Both expression simplifies to `(n)(n+1)(n+2)/6 = O(n^3)`