Quiz: Time Complexity Through One Function

Counting loop keywords cannot reveal the time complexity

Take A = [6, 2, 9, 1], so n = 4, and consider this function. It has three phases: a scan across the array, a nested phase whose inner bound depends on i, and a phase that doubles step. The function's time complexity cannot be classified until you inspect the bounds, update rules, and relationships between these loops.

int analyze(const vector<int>& A) {
    int n = A.size();
    int total = 0;

    for (int i = 0; i < n; i++) {
        total += A[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            total += 1;
        }
    }

    for (int step = 1; step < n; step *= 2) {
        total += step;
    }

    return total;
}

The first loop starts at i = 0, stops before i = n, and increases i by 1, so it visits every array position once. The second phase has an outer loop with the same bound, but its inner loop does not always run n times. Its upper bound is i, so the amount of work changes on every outer iteration. The final loop starts at 1 and doubles step, so its values do not increase one at a time.

The first and second phases are sequential: the second starts after the first finishes. The two loops inside the second phase are nested, so their work combines differently. The doubling phase comes after both of them. These relationships matter more than the fact that the function contains several loop keywords.

The nested phase executes 0 + 1 + 2 + 3 times, not 4 times 4

For n = 4, the outer loop takes i through 0, 1, 2, and 3. For each i, the inner loop starts at j = 0 and runs while j < i. When i = 0, there is no valid j. When i = 1, only j = 0 is valid. When i = 2, j = 0 and j = 1 are valid. When i = 3, j = 0, j = 1, and j = 2 are valid.

The six iterations are the sum 0 + 1 + 2 + 3. For a general input size n, the row counts are 0 + 1 + 2 + ... + (n - 1), which equals n(n - 1) / 2. The exact expression is about half of n squared, so its growth is quadratic. This is why the phase is O(n^2), even though no row performs n inner iterations.

Treating the phase as n times n would count excluded pairs such as (0, 0), (1, 1), and (1, 3). Those pairs never satisfy j < i. The changing inner bound is the reason the triangular count is smaller than a full n by n square, while still having quadratic growth.

Sequential phase costs are added, and the dominant term decides the result

The scan phase performs n iterations. The nested phase performs n(n - 1) / 2 iterations. The doubling phase has logarithmic growth because step takes values 1, 2, 4, 8, and so on until it reaches or passes n. For analyze, the combined cost can therefore be written as n + n(n - 1) / 2 + O(log n).

These costs are added because the phases run one after another. You do not multiply the scan cost by the nested cost or by the doubling cost. Among the added terms, n(n - 1) / 2 grows quadratically, while n is linear and O(log n) is logarithmic. The quadratic term is dominant, so analyze has time complexity O(n^2).

The array values change the result but not the loop counts

With A = [6, 2, 9, 1], the scan adds 6 + 2 + 9 + 1, producing 18. The nested phase adds 1 six times, producing 6 more. The doubling phase adds step values 1 and 2, producing 3 more. The function therefore returns 18 + 6 + 3 = 27.

The returned value and the operation count describe different things. The value 27 depends on the elements in A, but the iteration counts 4, 6, and 2 depend on n, i, j, and step. If you replace one array value while keeping n = 4, the scan's total changes, but every loop still follows the same bounds and update rules.

For example, changing 9 to another value would change the returned total because the first phase adds A[i]. It would not create or remove any iteration in the scan, the nested phase, or the doubling phase. The time complexity remains O(n^2), because its classification comes from how the loops scale with input size, not from the particular total produced for one array.