How to Calculate Time Complexity from Execution Counts

You calculate cost by counting executions, not by counting lines

A line that appears once in the source can execute many times. For a = [4, 2, 7, 1], select the two loop-body statements as the basic operations to count: sum += a[i] and prefixTotal += a[j]. The first loop visits one array position per i. The second loop visits positions from j = 0 through the current outer index i.

int a[] = {4, 2, 7, 1};
int n = 4;
int sum = 0;
int prefixTotal = 0;

for (int i = 0; i < n; i++) {
    sum += a[i];
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        prefixTotal += a[j];
    }
}

The first loop executes sum += a[i] once for each i from 0 through 3, so it executes 4 times. The nested block does not visit every pair of indices. When i is 0, the inner statement executes once. When i is 1, it executes twice. The complete count is 1 + 2 + 3 + 4 = 10, even though the statement prefixTotal += a[j] also appears only once in the source.

Consecutive blocks add their execution counts

The first loop finishes before the nested block starts. Its selected operation contributes n executions. The nested block then contributes its own executions. Since no iteration of one block overlaps an iteration of the other, their counts are added, not multiplied.

For this program, the cost of the selected operations has the shape n + inner-block count. Multiplication would describe work where every execution of one block causes every execution of another block. That is not what consecutive blocks do: the first block runs once through, then the second block runs once through.

The inner loop's bound determines how many nested iterations occur

The inner loop starts at j = 0 and continues while j <= i, so its number of executions changes with the outer index. For i = 0, only j = 0 is allowed. For i = 1, j = 0 and j = 1 are allowed. The same pattern gives three executions when i = 2 and four when i = 3.

For an input of size n, the outer indices produce inner counts 1, 2, 3, and so on through n. Therefore the nested block contributes 1 + 2 + ... + n executions. This arithmetic sum is n(n + 1)/2, not n * n. Two nested loops create a full n by n square only when the inner loop performs n iterations for every outer index.

The final complexity follows from the complete cost expression

Writing the selected operation counts together gives C(n) = n + n(n + 1)/2. If you count fixed setup or return work too, represent it with constants: C(n) = c0 + n + n(n + 1)/2 + c1. Those constants do not change the growth rate, but the complete expression shows where every counted part came from.

The variable part simplifies to n + (n^2 + n)/2 = (n^2 + 3n)/2. For n = 4, the unsimplified selected-operation count is 4 + 4(5)/2 = 4 + 10 = 14. The array values affect the totals stored in sum and prefixTotal, but they do not affect how many times the two selected statements execute.

The n^2 term is the dominant term, so the time complexity is Theta(n^2). The nested block is responsible for that growth. The first loop adds n work, but adding a linear term to a quadratic term does not change the final asymptotic classification.