Analyzing Time and Space Complexity of Java Loops

Hello again. In the previous lesson, you practiced a coding-interview workflow: clarify the contract, model the problem with examples and a baseline, choose and explain an approach, then trace it against edge cases. Complexity analysis gives the “why” behind many of those choices. It lets you say not merely that a solution works, but whether it will still work when an array has millions of elements.

This lesson develops a repeatable way to derive time complexity and space complexity for Java code with sequential and nested loops. By the end, you should be able to look at a loop structure, count its meaningful repetitions, simplify the resulting expression, and state an interview-ready complexity conclusion.

---

What complexity measures

Time complexity is the rate at which an algorithm’s work grows as input size grows. It is not a stopwatch measurement: the same Java code may run at different speeds on different machines, JVM configurations, or workloads. Complexity abstracts away those machine-specific differences and focuses on growth.

Let $n$ denote the input size. For an array problem, $n$ is usually nums.length.

If a loop executes once per array element and does constant work each time, its work is proportional to $n$:

$$T(n)=cn$$

Here $c$ represents a fixed amount of work per iteration, such as a comparison, assignment, or array access. In asymptotic analysis, we ignore fixed constant multipliers:

$$cn=\Theta (n)$$

In interviews, it is conventional to report this as $O(n)$ time. Strictly speaking:

• $O(f(n))$ is an asymptotic upper bound.
• $\Omega (f(n))$ is an asymptotic lower bound.
• $\Theta (f(n))$ means the growth rate is tightly bounded above and below by $f(n)$.

For a loop that always scans every element once, saying “$O(n)$ time” is accepted interview language, while “$\Theta (n)$ time” is more precise.

Two conventions will keep your analysis useful and consistent:

1. State the case being analyzed. Unless the interviewer asks otherwise, give worst-case time complexity. An early return may make a best case faster, but it does not erase the possible worst case.
2. Ignore constants and lower-order terms. For large $n$, $4n^2+20n+7$ grows like $n^2$, so it is $O(n^2)$.

This is not permission to ignore all detail. First derive a reasonable expression from the code; only then simplify it.

---

A three-step method for loop analysis

When code becomes longer, do not guess from how many for keywords you see. Use this process:

1. Define $n$. Identify what input quantity can grow: array length, string length, number of rows, and so on.
2. Count the dominant operation. Usually this is the work in the innermost loop body: a comparison, update, or method call.
3. Compose the counts. Add sequential blocks. For nested loops, determine how many times the inner body runs across all outer iterations. Then remove constants and lower-order terms.

The Princeton material gives a more detailed version of this idea, including exact operation counts before asymptotic simplification.

---

Sequential loops: add their costs

Consider a method that makes two independent passes through an input array.

public static int countPositivesAndSum(int[] nums) {
    int positiveCount = 0;
    int sum = 0;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            positiveCount++;
        }
    }

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }

    return positiveCount + sum;
}

Let $n=\text{nums.length}$.

The first loop may inspect all $n$ elements. Its time is $O(n)$. The second loop also inspects all $n$ elements, so its time is $O(n)$. The loops are sequential, meaning one completes before the other begins. Their costs are added:

$$T(n)=O(n)+O(n)+O(1)$$ $$T(n)=O(2n+1)$$

After dropping the constant multiplier and constant term:

$$T(n)=O(n)$$

A frequent error is to call this $O(n^2)$ because it contains two loops. That would be correct only if one loop ran fully inside every iteration of the other.

A useful spoken explanation is:

“There are two separate full passes through the array. Their work adds to $2n$, which simplifies to linear time, $O(n)$.”

The same logic applies to more sequential blocks:

Code pattern	Unsimplified work	Time complexity
One full scan	$n$	$O(n)$
Three full scans	$3n$	$O(n)$
A full scan plus all pairs	$n+n^2$	$O(n^2)$
A constant setup plus a full scan	$1+n$	$O(n)$

The largest-growing term dominates. It is not enough to count loops; you must determine the work each loop performs.

---

Nested loops: count the inner-body executions

Now consider code that checks every ordered combination of two array positions.

public static int countEqualPairs(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
    }

    return count;
}

The outer loop runs $n$ times. For each outer iteration, the inner loop runs $n$ times. The comparison in the body therefore runs:

$$n\cdot n=n^2$$

times. The time complexity is:

$$\Theta (n^2)$$

or, in typical interview phrasing, $O(n^2)$.

The critical wording is “for each outer iteration.” The inner index j resets to 0 every time i advances. This is why the work multiplies.

The supplied “Order of Growth” reference summarizes this standard pattern.

Dependent bounds: sum, do not blindly multiply

Not every nested loop executes exactly $n^2$ times. Consider the pair-checking baseline from the previous lesson:

public static int countZeroSumPairs(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == 0) {
                count++;
            }
        }
    }

    return count;
}

Here, j does not reset to 0. It starts at i + 1, so the number of inner iterations changes:

Outer index i	Inner-loop iterations
0	$n-1$
1	$n-2$
2	$n-3$
$\dots$	$\dots$
$n-1$	$0$

The total number of pair checks is:

$$(n-1)+(n-2)+\cdots +1+0$$

This is a triangular sum:

$$\frac{n(n-1)}{2}$$

After ignoring the coefficient $1/2$ and the lower-order term $-n/2$, the time complexity remains:

$$\Theta (n^2)$$

This implementation does roughly half as many comparisons as the version that includes every ordered pair, but both are quadratic. The precise count matters for practical performance; the asymptotic class matters when comparing how solutions scale.

For a triple nested loop where each loop can run across the full input, the same reasoning gives:

$$n\cdot n\cdot n=n^3$$

So its time complexity is $O(n^3)$. This becomes impractical rapidly as input size grows.

---

Nested loops are not automatically quadratic

The loop structure matters more than indentation. A nested loop is quadratic only when its combined number of iterations grows quadratically.

public static int countHalvingsForEachElement(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        for (int size = nums.length; size > 1; size /= 2) {
            count++;
        }
    }

    return count;
}

The outer loop executes $n$ times. The inner loop repeatedly halves size. After $k$ inner iterations:

$$\frac{n}{2^k}\le 1$$

This happens when $k$ is proportional to $\log n$. Therefore, the total time is:

$$O(n\log n)$$

You do not need to master every logarithmic pattern today. The key interview habit is to inspect the loop update:

• i++ across an input-sized range usually gives $O(n)$.
• size /= 2 usually gives $O(\log n)$.
• Nested costs combine according to the actual iteration counts.

This distinction will become especially useful when you study binary search and divide-and-conquer algorithms later in the course.

---

Space complexity: count memory that remains needed

Space complexity measures memory usage as the input grows. In coding interviews, report auxiliary space unless the interviewer says otherwise: memory used in addition to the input itself.

For this method:

public static int findMaximum(int[] nums) {
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }
    }

    return max;
}

The input array occupies $O(n)$ memory, but it was provided to the method. The method itself uses only a fixed number of variables: max and i. Their number does not grow with $n$.

• Time: $O(n)$
• Auxiliary space: $O(1)$

A loop variable does not become $O(n)$ space merely because its value changes $n$ times. Space concerns how much memory is simultaneously required, not how many times a variable is updated.

Allocating an array changes the space cost

public static int[] copyNegativesAsZero(int[] nums) {
    int[] result = new int[nums.length];

    for (int i = 0; i < nums.length; i++) {
        result[i] = Math.max(nums[i], 0);
    }

    return result;
}

The new result array has one slot per input element:

$$\text{Auxiliary space}=O(n)$$

The loop is still linear in time. Time and space are separate dimensions:

$$\text{Time}=O(n),\text{Auxiliary space}=O(n)$$

If an interviewer treats returned data separately, describe it clearly:

“The algorithm uses $O(n)$ space for the returned array. Apart from the output, it uses $O(1)$ auxiliary space.”

Nesting does not itself consume quadratic space

This code has quadratic time but constant auxiliary space:

public static int countPairsAboveTarget(int[] nums, int target) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] > target) {
                count++;
            }
        }
    }

    return count;
}

The nested loops do many operations, but the method retains only count, i, and j. Therefore:

$$\text{Time}=O(n^2),\text{Auxiliary space}=O(1)$$

By contrast, a two-dimensional allocation requires quadratic memory:

int[][] table = new int[n][n];

The table contains a number of entries proportional to $n^2$, so its space complexity is $O(n^2)$.

One Java-specific nuance is worth retaining: repeated allocation does not automatically mean all allocated objects coexist. If a loop creates a temporary int[n] array, processes it, and does not store a reference to it, the algorithm’s peak live auxiliary space can still be $O(n)$, even though total allocation work over the whole method may be larger. If the program stores every temporary array in a list, then those arrays remain live and the space can grow to $O(n^2)$.

---

A compact interview narration

When asked for complexity, give the reasoning before the result. For the pair-checking code, a strong explanation is:

“Let $n$ be the array length. The outer loop runs $n$ times. For each index, the inner loop checks later elements, so the total number of checks is $(n-1)+(n-2)+\dots +1$, which is $n(n-1)/2$. That is $O(n^2)$ time. The code uses only counters and loop indices beyond the input array, so auxiliary space is $O(1)$.”

That explanation demonstrates that you understand the code rather than reciting a pattern.

Before finalizing an answer, make four quick checks:

• What exactly is $n$?
• Are the loops sequential, independently nested, or nested with dependent bounds?
• Does any operation inside the loop have nonconstant cost or allocate growing storage?
• Am I reporting input space, auxiliary space, and output space clearly enough for the prompt?

---

Key takeaways

Complexity analysis is a disciplined counting exercise:

• Sequential blocks add. Two linear scans take $O(n+n)$, which simplifies to $O(n)$.
• Independent nested loops multiply. Two full $n$-iteration loops produce $O(n^2)$ time.
• Dependent inner bounds require a sum. A triangular count such as $1+2+\dots +n$ is still $O(n^2)$.
• Inspect updates, not just nesting. A halving loop is $O(\log n)$, so nesting it inside a linear loop gives $O(n\log n)$.
• Loop count and space are different. Nested loops can use $O(1)$ extra space; arrays, maps, lists, and matrices create space that grows with input size.

Next, you will use these tools to compare alternative solutions: when a hash-map solution is worth its extra memory, when a quadratic baseline is acceptable, and how practical implementation trade-offs affect the choice.