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

ignougroup
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(5sum_{j=0}^{n-1} j + sum_{j=0}^{n-1}7 right) – 7$
  4. $innerLoop = left(5sum_{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 = asum_{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