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
  • 3
    $\begingroup$ 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! $\endgroup$ – FrankW May 8 '14 at 9:05
  • $\begingroup$ 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... $\endgroup$ – conorgriffin May 8 '14 at 9:38
  • $\begingroup$ Did you see our reference question? $\endgroup$ – Raphael May 8 '14 at 9:59
  • $\begingroup$ The reference question is about how to get an initial formula, this question is about simplifying the formula. $\endgroup$ – FrankW May 8 '14 at 22:05
  • $\begingroup$ 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. $\endgroup$ – 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$.

  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.$$
  • $\begingroup$ 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). $\endgroup$ – Guildenstern May 8 '14 at 10:01
  • $\begingroup$ Now it makes sense! So the paper is incorrect, thanks for your clear and comprehensive answer. $\endgroup$ – conorgriffin May 8 '14 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.