Analyzing Time and Auxiliary-Space Complexity of Iterative C++ Code

Hello! Last lesson, you chose between passing a vector by value and by reference, and between copying or referencing each element in a range-based loop. Those choices affect not just what a function may change, but how much work and memory it needs.

In this lesson, you’ll determine the asymptotic time and auxiliary-space complexity of iterative C++ functions. The goal is to look at a function and give an interview-ready explanation of its cost, including work that a copy or a library call might hide.

Measure growth, not seconds

Suppose a function scans a vector of $n$ integers. Its elapsed time will vary between computers, but the number of elements it examines grows with $n$. Time complexity describes how the amount of work scales as the input grows. We usually state the worst case: among inputs of the same size, how much work might the function perform?

Consider:

long long sumValues(const std::vector<int>& values) {
    long long sum = 0;
    for (int value : values) {
        sum += value;
    }
    return sum;
}

Let $n$ be values.size(). The loop visits $n$ elements, doing a constant amount of work for each. Initialization and return add only constant work. We report $O(n)$ time: for large $n$, the term proportional to $n$ describes the growth. We do not need an exact instruction count.

The notation deserves one qualification: Big-O is an upper bound. An $O(n)$ function is technically also $O(n^2)$, but $O(n)$ is the more informative answer. In an interview, aim for the tightest bound you can justify.

Read the selected parts of Cornell CS 2110’s Analyzing Complexity to see why constants and lower-order terms disappear, and why a useful Big-O answer seeks a tight bound.

The input size must be explicit. For one vector, $n$ can mean its length. For two vectors of potentially different lengths, use $n$ and $m$ rather than silently assuming they match.

Count how often the body actually runs

The reliable way to analyze a loop is to identify its starting value, stopping condition, update, and the cost of its body. Abdul Bari’s 1.5.1 Time Complexity #1 traces several loops this way. The triangular-loop example is particularly useful because its inner loop does not run the same number of times on every outer iteration.

A fixed step size changes a count by a constant factor, not its Big-O class. A loop that visits indices 0, 2, 4, ... visits roughly $n/2$ elements, so it is still $O(n)$.

For nested loops, first check whether the inner loop runs a fixed number of times per outer iteration:

std::size_t countMatches(const std::vector<int>& a,
                         const std::vector<int>& b) {
    std::size_t count = 0;
    for (int x : a) {
        for (int y : b) {
            if (x == y) {
                ++count;
            }
        }
    }
    return count;
}

If a has $n$ elements and b has $m$, the comparison runs $nm$ times. Integer comparisons and increments take constant time, so the function is $O(nm)$ time. Only if both lengths are described by the same $n$ would you call it $O(n^2)$.

Now change the inner bound:

std::size_t countIncreasingIndexPairs(const std::vector<int>& values) {
    std::size_t count = 0;
    const std::size_t n = values.size();

    for (std::size_t i = 0; i < n; ++i) {
        for (std::size_t j = i + 1; j < n; ++j) {
            if (values[i] < values[j]) {
                ++count;
            }
        }
    }
    return count;
}

The inner body runs $n-1$ times for the first i, then $n-2$, and eventually zero times. Across the function, it runs

times. Its worst-case time is $O(n^2)$. The loops are not each doing $n$ iterations on every pass, but the total still grows quadratically.

Not every loop advances one step at a time. Here the remaining quantity is halved:

std::size_t halvings(std::size_t n) {
    std::size_t count = 0;
    while (n > 1) {
        n /= 2;
        ++count;
    }
    return count;
}

For $n\ge 2$, it takes on the order of $\log n$ halvings to reach one, so the time is $O(\log n)$. By contrast, a loop that subtracts two each time is still $O(n)$: it removes a fixed amount rather than a fixed fraction.

Finally, distinguish nested work from sequential work. Scanning an $n$-element vector and then an $m$-element vector costs $O(n+m)$, not $O(nm)$. For sequential parts, add their costs; for repeated work inside a loop, account for that work on every iteration. For example, a linear scan followed by the quadratic pair-counting loop costs $O(n+n^2)=O(n^2)$.

Look inside the C++ operations

A short line of code is not necessarily constant-time work. Last lesson’s parameter choices provide an immediate example:

long long sumByReference(const std::vector<int>& values) {
    long long sum = 0;
    for (int value : values) {
        sum += value;
    }
    return sum;
}

long long sumByValue(std::vector<int> values) {
    long long sum = 0;
    for (int value : values) {
        sum += value;
    }
    return sum;
}

When called with an existing vector, both functions take $O(n)$ time overall. But sumByValue first copies $n$ integers into its own vector; sumByReference does not. Their time classes match, while their extra-memory costs differ. Passing by value may behave differently for a temporary that can be moved, so when analyzing a call, say what kind of argument you assume.

Likewise, for (int value : values) copies one inexpensive integer per iteration. If the elements were large strings, copying each string could make the body’s cost depend on string length. A const auto& loop variable avoids those element copies when the function only needs to read them.

Apply the same scrutiny to operations inside a loop. You already know that std::sort is $O(n\log n)$ for $n$ elements and std::reverse is $O(n)$. Placing either call on a line does not make it $O(1)$. State the cost of relevant calls, copies, and allocations before combining them with the loop count.

Count extra memory at its peak

Auxiliary space is memory the algorithm needs in addition to the supplied input. A reference to a caller-owned vector does not duplicate its elements. A vector copied by value does require storage for another $n$ elements.

Read the “Space Complexity” subsection of Cornell’s Analyzing Complexity. Its examples use Java, but the distinction between input storage and extra working storage also applies to the C++ functions here. Stop before its Java-specific string-concatenation example.

In sumByReference, the accumulator and loop variable occupy a constant amount of extra space, regardless of $n$: $O(1)$ auxiliary space. In sumByValue, a call with an existing vector makes a copy containing $n$ integers: $O(n)$ auxiliary space. The input’s original storage is excluded; the new copy is not.

A loop may execute many times without retaining more memory each time. countIncreasingIndexPairs performs $O(n^2)$ work but keeps only count, n, i, and j: its auxiliary space is $O(1)$. Conversely, creating a scratch vector of $n$ integers requires $O(n)$ auxiliary space even if the function uses only one loop.

If a function produces a new vector that the caller needs, state your convention clearly. You might report “$O(1)$ working space excluding the required output, and $O(n)$ additional storage including it.” This avoids an apparent disagreement caused solely by whether output storage was counted.

An interview explanation can now follow a compact pattern: define the input size, identify the repeated and hidden work, give the worst-case time, then identify the maximum extra storage held at once.

Takeaways

To analyze iterative C++ code, count iterations from the actual bounds, include the cost of each loop body, and distinguish sequential from nested work. Drop constant factors and lower-order terms when reporting the tightest useful Big-O bound. For auxiliary space, exclude the supplied input but count copies and scratch storage; measure the peak held at one time, not how often memory is allocated.

Next, you’ll apply this method to common C++ STL containers, where an operation’s average-case cost may differ from its worst-case cost.