On average, as a function of n, how many print statements are executed by the following algorithm?

Question

On average, as a function of n, how many print statements are executed by the following algorithm?

For i = 1 to n

    For j = i to n

        For k=1 to n print(i, j, k);

a. n(n+1)/2

b. n^3

c. n^2 * ((n-1)/2)

d. n^2 * ((n+1)/2)

I find this problem a little confusing, however what I think is, there will be n + n + n... till i = n print outs, which is like n^2 terms printed out, however from here I am kinda stuck on what to do next if I'm on the right track.

Answer 1

The $i$ and $j$ loops combine to give iterations to the triangular number of $n$, since $j$ is iterated by one less each time. This is $n(n+1)/2$ loops. Then the $k$ loop iterates $n$ times inside that, so the total print count is $n^2(n+1)/2$.

Another way to view it is that the $i$ and $k$ loops iterate $n$ times, and the $j$ loop iterates somewhere between $1$ and $n$ times, with an even spread, averaging $\frac{n+1}{2}$ times. Total answer, again, $n\cdot\frac{n+1}{2}\cdot n=n^2(n+1)/2$