mercredi 6 mai 2015

Counting the basic operations of a given program

I am looking at the following: Operations Counting Example

Which is supposed to present the operations count of the following pseudocode:

Algorithm prefixAverages(A)
 Input array A of n numbers
 Output array B of n numbers such that B[i] is the average
 of elements A[0], A[1], … , A[i]

for i = 0 to n - 1 do
   b = 0
   for j = 0 to i do
       b = b + A[j]
       j++;
   B[i] = b / (i + 1)
return B

But I don't see how the counts on the inner for loop are reached. It says that for case i=0; j=0; the inner for loop runs twice? But it strikes me that it should only run once to see that 0 < 0. Can anyone provide insight into where the given operations count comes from or provide their own operations count?

This is under the assumption that primitive operations are:

  • Assignment
  • Array access
  • Mathematical operators (+, -, /, *)
  • Comparison
  • Increment/Decrement (math in disguise)
  • Return statements

Let me know if anything is unclear or you need more information

Aucun commentaire:

Enregistrer un commentaire