Can someone show me step-by-step how to calculate the primitive operations of this algorithm?

Problem Detail: 

See the example algorithm below from my course notes, I don't follow the operation counting in the inner loop. Can someone walk me through this step-by-step?

Here's the algorithm:

Algorithm PrefixAverages1(A, n):     Input: An integer array A of size n.     Output: An array X of size n such that X[j] is the average of A[0] to A[j]      Let X be an integer array of size n         1     for j=1 to n-1 do                           2         a <- 0                                  3         for k=1 to j do                         4             a <- a + A[k]                       5         X[j] <- a/(j+1)                         6     return X                                    7 

The solution provided to this sample question uses the following steps to calculate the total cost (in primitive operations*) of the running time of the algorithm:

Operation counting for main body and outer loop:

• $1 + op(outerLoop) + 1$
• $2 + op(outerLoop)$
• $2 + (1 + (B-A + 2)op(j>n-1) + (B-A + 1) * 2 + op(innerLoop))$ where $B = (n-1)$ and $A = 1$
• $2 + 1 + 2n + (n-1) * 2 + op(innerLoop)$
• $1 + 4n + op(innerLoop)$

Operation counting for inner loop:

1. $innerLoop = \sum_{j=1}^{n-1} 5j + 7$
2. $innerLoop = \left(\sum_{j=0}^{n-1} 5j + 7 \right) - 7$
3. $innerLoop = \left(5\sum_{j=0}^{n-1} j + \sum_{j=0}^{n-1}7 \right) - 7$
4. $innerLoop = \left(5\sum_{j=0}^{n-1} j + 7n \right) - 7$
5. $innerLoop = \frac{5n^2}{2} + 7n - 7$

Then putting the cost of the inner loop and the main body together, the total cost is shown as:

• $\frac{5n^2}{2} + 11n -6$

Specifically I don't follow the operation counting for the inner loop, I understand why there's a $- 7$ added when the sum is changed from $j=1$ to $j=0$. But I don't quite understand the subsequent steps that manipulate the equation.

---

Source: This is a previous exam paper from my University course.

* List of primitive operations:

• Indexing into an array
• Assignment
• Arithmetic
• Method call
• Following an object reference
• Comparison
• Returning a value

Asked By : conorgriffin

Answered By : FrankW

I'll list the arithmetic rules used in each step. In the following $f$ and $g$ are terms that possibly depend on $i$, while $a$ doesn't depend on $i$.

1. has no operations.
2. you explained in the question.
3. $$\sum_{i=x}^y f+g = \sum_{i=x}^y f + \sum_{i=x}^y g$$ and $$\sum_{i=x}^y af = a\sum_{i=x}^y f.$$
4. $$\sum_{i=x}^y a = (y-x+1)a.$$
5. is wrong. The correct formula to apply would be $$\sum_{i=0}^y i = \frac{y(y+1)}2,$$ making the result from the question $$x = \frac{5n(n-1)}2 + 7n - 7 = \frac 52 n^2 + \frac 92 n -7.$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24526