1

I've written a piece of java code that when given an array (arrayX), works out the prefix averages of that array and outputs them in another array (arrayA). I am supposed to count the primitive operations and calculate the Big-O notation (which i'm guessing is the overall number of calculations). I have included the java code and what I believe to be the number of primitive operations next to each line, but I am unsure whether I have counted them correctly. Thanks in advance and sorry for my inexperience, i'm finding this hard to grasp :)

double [] arrayA = new double [arrayX.length]; *(3 Operations)*

    for (int i = 0; i < arrayX.length; ++i) *(4n + 2 Operations)* 
    {
        double sum = arrayX[i]; *(3n Operations)*

        for (int j = 0; j < i; ++j) *(4n^2 + 2n Operations)*
        {
            sum = sum + arrayX[j]; *(5n^2 Operations)*
        }
        arrayA[i] = sum/(i+1); *(6n Operations)*
    }
    return arrayA; *(1 Operation)*

Total number of operations: 9n^2 +15n + 6

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
Phillip
  • 59
  • 3
  • 9
  • 1
    You've got the right idea, but the fundamental concept behind Big-O notation is that we're interested in the order of operations, not the literal quantity. [This question](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) may help shed some light on the concept. – x4nd3r Nov 12 '14 at 22:58

1 Answers1

3

I don't think there's any standard definition of "what constitutes a primitive operation". I'm assuming this is a class assignment; if your instructor has given you detailed information about what operations to count as primitive operations, then go by that, otherwise I don't think he can fault you for any way you count them, as long as you have a reasonable explanation.

Regarding the inner loop:

for (int j = 0; j < i; ++j)

please note that the total number of times the loop executes is not n2, but rather 0+1+2+...+(n-1) = n(n-1)/2. So your calculations are probably incorrect there.

Big-O notation is not really "the total number of calculations"; roughly speaking, it's a way of estimating how the number of calculations grows when n grows, by saying that the number of calculations is roughly proportional to some function of n. If the number of calculations is Kn2 for any constant K, we say that the number of calculations is O(n2) regardless of what the constant K is. Therefore, it doesn't completely matter what you count as primitive operations. You might get 9n2, someone else who counts different operations may get 7n2 or 3n2, but it doesn't matter--it's all O(n2). And the lower-degree terms (15n+6) don't count at all, since they grow more slowly than the Kn2 term. Thus they aren't relevant to determining the appropriate big-O formula.

ajb
  • 31,309
  • 3
  • 58
  • 84
  • So would that mean the operation count for the inner for loop would be as follows: for (int j = 0; j < i; ++j) *(4(n(n-1)/2) Operations)* sum = sum + arrayX[j]; *(5(n(n-1)/2) Operations)* – Phillip Nov 12 '14 at 23:29
  • @Phillip I'm not sure, since I really don't know what you're counting as an operation. I'm afraid I can't help you here. Please do remember that if the body of the loop is performed M times, the `j < i` check will be performed M+1 times. – ajb Nov 12 '14 at 23:37
  • Ok so the loop itself will be run n(n-1)/2 and will everything inside the body of the loop, and then any operations will be added to that. I'm confused about where the /2 part has come from? – Phillip Nov 12 '14 at 23:41
  • @Philip Since the inner loop stops at `j < i`, that means that when `i=0` the body of the loop executes 0 times, when `i=1` it executes 1 time, when `i=2` it executes 2 times and so on. Therefore the total number of times it executes is 0+1+2+...+(n-1) (since n-1 is the largest value of `i`). The formula for this sum is n(n-1)/2--that's just algebra. Look up [Arithmetic progression](http://en.wikipedia.org/wiki/Arithmetic_progression) if you don't know how this formula is derived. – ajb Nov 12 '14 at 23:51