For the psuedocode:
Code: Select all
for(int i = 0; i < n; i++)
for(int j = i; j <= n; j++)
for(int k = i; k <= j; k++)
sum++;Line 4 executes only when k <= j. k ranges from i to j, inclusive. j ranges from i to n, inclusive. i ranges from 0 to n-1, inclusive.
Let's follow the process to find the pattern, starting with i = 0:
When i = 0, j ranges from 0 to n. k ranges from 0 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n+1 times in the last loop.
When i = 1, j ranges from 1 to n. k ranges from 1 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n times in the last loop.
…
This continues until i = n-1. The range of k decrements by 1 in each iteration of the loop on line 2. So, line 3 is executed 1 less time for each iteration of the loop on line 2. Since i does not range all the way to n, j and k will never start at n, meaning that that there will never be a time when lines 3 & 4 are only executed once in a loop. My equation at this point for the number of times that line 4 is run is as follows:
Code: Select all
T[size=70]4[/size] = (1+2+3+ … +(n-1)+n+(n+1)) + (1+2+3+ … +(n-1)+n) + (1+2+3+ … +(n-1)) + … + (1+2+3) + (1+2)- factoring the terms by iterations, and
- factoring the terms by common terms.
Code: Select all
T[size=70]4[/size] = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(3)(4) + ½(2)(3)
T[size=70]4[/size] = ½[(n+2)(n+1) + (n+1)(n) + (n)(n-1) + … + (4)(3) + (3)(2)]The other approach was to group like terms (i.e. (n+1), n, (n-1), etc):
Code: Select all
T[size=70]4[/size] = (n-1)(1) + (n-1)(2) + (n-2)(3) + (n-3)(4) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + 1(n+1)
T[size=70]4[/size] = 1(n-1) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + (n+1)
T[size=70]4[/size] = [1(n) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n)] + (n+1) - 1
T[size=70]4[/size] = [(n+1) + 3(n) + 5(n-1) + 7(n-2) + 9(n-3) + …] - 1Any help would be appreciated. ^^