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.