int x = 0; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) for (int
ID: 3641571 • Letter: I
Question
int x = 0;for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
for (int k = j + 1; k < N; k++)
x++;
How many times does the inner loop execute? This is the same as the value of x at the end of this code segment.
Answer is: N(N-1) (N-2) / 6.
I, too, can get this answer using combinatorics. However, I'm interested in an answer that looks more like this:
http://www.cramster.com/answers-apr-12/computer-science/times-loop-exec-1for-i1-nfor-j1-1for-k1-1snext-knext-jne_2377629.aspx?rec=0
Explanation / Answer
For a given value of j, the k-loop will run from j+1 to N-1, which is (N-1)-(j+1)+1 = N-1-j times. For a given value of i, j will be incremented from i+1 to N-1, which gives the total number of times the k-loop will run as (N-1-(i+1))+(N-1-(i+2))+...+(N-1-(N-1)) = (N-2-i) + (N-2-(i+1)) + ... + 1 + 0. Therefore, it will run (N-2-i)(N-1-i)/2 = (N2-2N-Ni-N+2+i-Ni+2i+i2)/2 = (N2-3N+2)/2 + i(3-2N)/2 + i2/2 times for a given value of i. Now we just sum this over the possible values of i from 0 to N-3. We ignore i = N-2 and N-1, since N>k>=i+2 implies that i<N-2.
The sum of (N2-3N+2)/2 as i increments from 0 to N-3 is independent of i, so it is just (N-2)(N2-3N+2)/2 = (N3-5N2+8N-4)/2.
The sum of i(3-2N)/2 as i increments from 0 to N-3 is equal to (0+1+...+(N-3))(3-2N)/2 = (N-2)(N-3)(3-2N)/4 = (N2-5N+6)(3-2N)/4 = (-2N3+13N2-27N+18)/4.
The sum of i2/2 as i increments from 0 to N-3 is equal to (0 + 12 + ... + (N-3)2)/2 = (N-3)(N-2)(2N-5)/12 = (N2-5N+6)(2N-5)/12 = (2N3-15N2+37N-30)/12.
Now we add all of these together to get (N3-5N2+8N-4)/2 + (-2N3+13N2-27N+18)/4 + (2N3-15N2+37N-30)/6= (6N3-30N2+48N-24)/12 + (-6N3+39N2-81N+54)/12 + (2N3-15N2+37N-30)/12 = (2N3-6N2+4N)/12 = (N3 - 3N2 + 2N)/6 = N(N2-3N+2)/6 = N(N-1)(N-2)/6
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.