1

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.

Hyune
  • 101
  • I am assuming you have a sequence of nested loops. Note that each loop is iterated $n$ times. For each iteration of the outermost loop, the second outermost loop is iterated $n$ times. Similarly, for each iteration of the second outermost loop, the innermost loop is iterated $n$ times. Therefore exactly $n \times n \times n = n^3$ print statements are executed. – Vizuna Mar 17 '15 at 02:20
  • A word about format: Note that when you indent by 4 or more spaces, you get typewriter text on a gray background (which is good here, because it looks like a computer program listing might look). But you have to put at least 4 spaces (you can put more) in front of every line of your program in order to make it look consistent. This gray-box format also takes the end of each line you type quite literally, so you only have to press Enter once, not twice, to ensure that the next thing comes out on a new line. If you press Enter twice then you end up with a blank line in the listing. – David K Mar 17 '15 at 02:35
  • ah I see, I think my flaw was in understanding how nested for loops work, I get what you mean.

    But if for example i = 3, then j would get iterated from 3 to n not from 1 to n, surely this must have an impact on our result? Maybe you didn't see the j = i to n because of the way I presented the question (my bad)

     – Hyune Mar 17 '15 at 02:39
  • Yeah, I misread it as $j = 1$ to $n$. Note that the $j$ loop iterates a total of $n + (n - 1) + \ldots + 1 = \frac {n(n + 1)}{2}$ times, which means the $k$ loop iterates a total of $\frac{n^2(n + 1)}{2}$ times. Since the print statements only occur in the $k$ loop, the total number of iterations of the $k$ loop gives your desired answer. – Vizuna Mar 17 '15 at 03:08

1 Answers1

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$

Joffan
  • 39,627
  • Yes I made a program to confirm this result, however I still cannot get an intuitive feel for how you managed to get n(n+1)/2 loops. Would it be possible to explain it in another way?

    I understand that i must iterate n times, I also understand that j must iterate 1 less after each iteration of i meaning that j would iterate n - 1 if i = 2 , n -2 iterations if i = 3 and so on

     – Hyune Mar 17 '15 at 03:06
  • $n + (n - 1) + (n - 2) + \ldots + 1$ is the total number of iterations of the $j$ loop. Coincidentally, this is an arithmetic progression, which evaluates to $\frac{n(n + 1)}{2}$. – Vizuna Mar 17 '15 at 03:12
  • Thank you very much, I am now confident about this problem :) – Hyune Mar 17 '15 at 03:24
  • 1
    answer update with anothr way of looking at it – Joffan Mar 17 '15 at 03:28