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