Thread: Calculating Big O

The second picture should be along the right hand side of the first picture. I apologize for not shrinking it before pasting.

In the above program, I don't understand why both the inner loop total and total for the entire program includes fractions. Ie. 3/2n^2 -1/2n for the inner loop and 3/2n^2 +5/2n +3 for the total.
For my answer, I multiplied inner loop total of (3n +1) by (n+1) which is the number of times the outer loop iterates to get a total of 3n^2+4n+1. Tack on 2 for initialization and return 0 for a grand total of 3n^2 +4n +3 rather than the equation given.

From my answer, if I drop the coefficients and low order terms, I still end up with O(n^2) which is the correct answer.

Also, what if the nested loop had a constant in the conditions, ie. for(int i=0; i<3; i++) such as below:

Code:

for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                printf("%d", arr[i]);
               }
            printf("\n");
        }
}

In this case, I'd imagine that it is not quadratic but linear since the iterations in the nested loops are limited to a constant and would not increase as n increases.