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

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 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
• Don't use images as main content of your post. It makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – FrankW May 8 '14 at 9:05
• No problem, I've added the important steps in the equation. I'm not sure how I can format the problem appropriately. Maybe just in raw fixed-width text... – conorgriffin May 8 '14 at 9:38
• Did you see our reference question? – Raphael May 8 '14 at 9:59
• The reference question is about how to get an initial formula, this question is about simplifying the formula. – FrankW May 8 '14 at 22:05
• Is this still a poorly formatted question? Just asking since it got down votes. I've improved it from the original so just want to see if it's still under-par. – conorgriffin May 9 '14 at 8:42

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$.
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.$$
• Something for readers to note about 5.: this formula is attributed to Gauss, and the idea behind it can be seen by noticing the symmetry you get when adding numbers $1$ to $y$ (pairwise add together numbers at opposite ends in the sum). – Guildenstern May 8 '14 at 10:01