Analyzing Time and Space Complexity in JavaScript Loops and Recursion

Hello. In the previous lesson, you used input constraints to judge whether a brute-force approach is affordable, then derived Two Sum’s $O(n^2)$ pair scan before identifying its repeated complement search.

Now we will make complexity analysis a repeatable code-reading skill. By the end, you should be able to look at a JavaScript function with loops or recursion and state its worst-case time complexity and auxiliary-space complexity, with a brief justification. This is the level of explanation expected when an interviewer asks, “What are the time and space costs?”

---

What complexity measures—and what it deliberately ignores

Let $n$ represent the size of the relevant input. For an array problem, $n$ is usually arr.length; for a string, it is usually str.length. If a function accepts two independently sized arrays, name both sizes, such as $a$ and $b$, rather than silently assuming they are equal.

Time complexity describes how the number of meaningful operations grows as input size grows. It does not mean the elapsed milliseconds on your laptop. Browser, Node.js version, hardware, and background processes affect timing; asymptotic analysis focuses on growth.

Auxiliary space is the additional memory an algorithm allocates while it runs, excluding the input itself. In interview settings, we also normally exclude the returned output unless the interviewer explicitly asks for total space.

For example:

function sumArray(nums) {
  let total = 0;

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

  return total;
}

The input array nums is already supplied, so it does not count as auxiliary memory. The function allocates total and i, a constant number of primitive variables:

$$\text{auxiliary space}=O(1)$$

The loop may visit every element, so its worst-case time is:

$$\text{time}=O(n)$$

A useful convention: in interview conversation, people commonly say “Big O” for the dominant worst-case growth rate. Technically, many of the examples below are also tight bounds, written $\Theta (n)$ or $\Theta (n^2)$. Stating $O(n)$ with a correct justification is the expected practical answer.

---

The mechanical method for loops

When analyzing a loop, do not label it from its syntax alone. A for loop is not automatically $O(n)$; you need to determine:

1. What variable controls the number of iterations?
2. How many times can the loop body execute?
3. What is the cost of the body per iteration?
4. Are loops sequential, nested, or dependent on one another?

We make the standard interview-model assumption that simple arithmetic, comparisons, assignments, and array indexing such as nums[i] cost $O(1)$. Be alert, however, when the body calls a helper or library method whose cost grows with input size.

One full pass: linear time

function hasNegative(nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0) {
      return true;
    }
  }

  return false;
}

The function might return immediately if nums[0] is negative. That is its best case. But if no negative value exists, it checks all $n$ elements:

$$T(n)=cn+d$$

where $c$ and $d$ are constants representing the work per iteration and setup work. We discard constant factors and lower-order terms:

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

An early return does not change the worst-case complexity unless the problem specifically asks for best-case behavior.

The function uses a loop index and no growing data structure:

$$S(n)=O(1)$$

Sequential loops add, then simplify

function minAndMax(nums) {
  let min = Infinity;
  let max = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    min = Math.min(min, nums[i]);
  }

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

  return [min, max];
}

The first loop costs $O(n)$. The second costs another $O(n)$. They are adjacent, not nested:

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

Do not multiply merely because you see two loops.

The returned two-element array has constant size, so even if you count output memory, it is $O(1)$. Auxiliary space is also $O(1)$.

Nested loops usually multiply

function countEqualPairs(nums) {
  let count = 0;

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

  return count;
}

For each of $n$ outer-loop iterations, the inner loop completes $n$ iterations. The comparison runs:

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

times. Therefore:

$$T(n)=O(n^2)$$

The two loop counters and count remain a fixed number of variables:

$$S(n)=O(1)$$

This multiplication rule applies because the entire inner loop runs for every outer-loop iteration.

Dependent inner loops: count the total, not just the syntax

Now consider the pair scan from the previous lesson:

function hasPairWithSum(nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return true;
      }
    }
  }

  return false;
}

The inner loop does not always run $n$ times. Its iterations shrink:

• when i is 0, it runs about $n-1$ times;
• when i is 1, it runs about $n-2$ times;
• near the end, it runs only a few times.

The total is:

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

which equals:

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

The factor of one half does not change the growth class:

$$T(n)=O(n^2)$$

This is still quadratic, even though it avoids duplicate pairs and self-pairing. Its auxiliary space remains $O(1)$.

---

Common loop patterns worth recognizing

The following table is a compact pattern reference. Use it after you have identified the loop bounds and body cost.

Code pattern	Iteration count	Time contribution
for (let i = 0; i < n; i++)	$n$	$O(n)$
for (let i = 0; i < 1000; i++)	fixed constant	$O(1)$
Two full loops, one after another	$n+n$	$O(n)$
One full loop nested inside another	$n\cdot n$	$O(n^2)$
Counter doubles each iteration	about ${\log }_{2}n$	$O(\log n)$
Full loop containing a doubling loop	$n\log n$	$O(n\log n)$

A fixed-size loop is $O(1)$, even if the fixed number is large:

for (let attempt = 0; attempt < 1000; attempt++) {
  // constant work
}

It may be expensive in real wall-clock terms, but increasing the input size does not increase its iteration count.

A loop that repeatedly doubles its counter is logarithmic:

function countDoublings(n) {
  let steps = 0;

  for (let size = 1; size < n; size *= 2) {
    steps++;
  }

  return steps;
}

The values of size are $1$, $2$, $4$, $8$, and so on. After $k$ iterations:

$$2^k\ge n$$

Thus:

$$k\ge {\log }_{2}n$$

and the time complexity is:

$$O(\log n)$$

The base of the logarithm is irrelevant in Big O because different constant bases differ only by a constant factor.

Do not hide expensive work inside a loop body

This is a common JavaScript interview mistake:

function containsDuplicateSlow(nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums.indexOf(nums[i]) !== i) {
      return true;
    }
  }

  return false;
}

The outer loop can run $n$ times. indexOf may scan up to $n$ elements each time. Therefore, in the worst case:

$$T(n)=O(n)\cdot O(n)=O(n^2)$$

The code has only one visible for loop, but its body contains another linear search.

For the same reason, be cautious with operations such as:

• arr.includes(value), which can cost $O(n)$;
• arr.indexOf(value), which can cost $O(n)$;
• arr.slice(...), which copies a portion of an array and can cost proportional to the copied length;
• sorting, which commonly costs $O(n\log n)$ for comparison sorting.

You will analyze sorting explicitly in the next lesson. For now, the habit is simple: a method call is not automatically $O(1)$.

---

Auxiliary space: track memory that grows

Loops by themselves generally do not use more than constant auxiliary space. A loop runs many times, but it normally reuses the same variables.

function squareInPlace(nums) {
  for (let i = 0; i < nums.length; i++) {
    nums[i] = nums[i] * nums[i];
  }

  return nums;
}

This mutates the input array rather than allocating another array. The extra memory is only i and temporary primitive values:

$$S(n)=O(1)$$

Contrast it with a function that creates a new array:

function squaredCopy(nums) {
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    result.push(nums[i] * nums[i]);
  }

  return result;
}

result grows to hold $n$ values:

$$S(n)=O(n)$$

Even though the result is returned, an interviewer may distinguish between:

• Auxiliary space: $O(n)$, because the algorithm constructs result.
• Output space: also $O(n)$.

In most problem discussions, simply say “$O(n)$ extra space for the output array.” If the prompt requires an “in-place” solution, that requirement is usually asking you to target $O(1)$ auxiliary space.

Common extra-memory patterns include:

Allocated structure	Maximum size	Auxiliary space
A few variables, indices, pointers	constant	$O(1)$
New array containing one item per input item	$n$	$O(n)$
Set or Map storing up to every input item	$n$	$O(n)$
Matrix with $n$ rows and $n$ columns	$n^2$	$O(n^2)$

---

Recursion has two separate questions: total calls and maximum depth

With recursion, learners often confuse the total number of calls with the number of calls simultaneously stored on the call stack. Keep them separate:

• Time: count the total work across all calls.
• Auxiliary space: find the maximum number of active stack frames at one moment, then account for memory held by each frame.

One recursive call with a shrinking input

function recursiveSum(n) {
  if (n <= 0) {
    return 0;
  }

  return n + recursiveSum(n - 1);
}

Each non-base call performs constant work and makes exactly one call with a smaller argument. The chain is:

recursiveSum(n)
recursiveSum(n - 1)
recursiveSum(n - 2)
...
recursiveSum(0)

There are proportional to $n$ calls:

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

So:

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

Before the base case returns, there are proportional to $n$ active calls waiting for their recursive result. Each stack frame stores a constant amount of information, so:

$$S(n)=O(n)$$

This is a crucial distinction from an iterative loop that performs the same summation. The iterative version would usually have $O(n)$ time but $O(1)$ auxiliary space.

Two recursive calls can create exponential time

Now examine this intentionally simple function:

function dib(n) {
  if (n <= 1) {
    return;
  }

  dib(n - 1);
  dib(n - 1);
}

Each call above the base case makes two recursive calls, each only one level smaller. The recurrence is:

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

At the first level there is one call. At the next, there are two. Then four, then eight. The total number of calls grows exponentially:

$$T(n)=O(2^n)$$

The recursion tree is useful for time, because it represents every call eventually made. But it is not a picture of all memory being active at once. JavaScript evaluates the first dib(n - 1) call completely, returns from it, and only then evaluates the second call.

At any one time, execution follows just one path from the root toward a base case. That longest path has depth proportional to $n$:

$$S(n)=O(n)$$

So this function has:

$$\text{time}=O(2^n),\text{auxiliary space}=O(n)$$

This combination is common in naive recursive search: huge repeated computation, but a stack depth that grows only linearly.

Stack depth is not enough if each call allocates growing data

The shortcut “recursion depth $n$ means $O(n)$ space” assumes each frame contains only $O(1)$ extra data. Consider this pattern:

function processSuffixes(nums) {
  if (nums.length === 0) {
    return;
  }

  const rest = nums.slice(1);
  processSuffixes(rest);
}

The function has linear recursion depth, but every slice(1) allocates a new array. Before the deepest call returns, multiple copied suffixes can be alive at once. Their lengths are roughly:

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

That sum is quadratic:

$$S(n)=O(n^2)$$

You do not need to memorize this particular example. The principle is what matters: analyze both recursion depth and what each frame allocates.

---

A reliable interview explanation template

When reading an unfamiliar solution, narrate the analysis in this order:

1. Define the input size.
   “Let $n$ be nums.length.”

2. Count the dominant repeated work.
   “The outer loop runs $n$ times, and the inner loop completes $n$ iterations for each outer iteration.”

3. Combine costs correctly.

   • sequential blocks add;
   • nested full loops multiply;
   • dependent loop bounds may require a sum;
   • recursive calls require counting the full call tree.

4. Simplify asymptotically.
   Drop constant factors and lower-order terms:

   $$O(3n^2+7n+10)=O(n^2)$$

5. Inventory extra memory.
   “It uses only counters and scalar variables, so auxiliary space is $O(1)$.”
   Or: “The Map can hold one entry per element, so auxiliary space is $O(n)$.”
   Or: “The recursion reaches depth $n$, so the call stack uses $O(n)$.”

For the brute-force Two Sum code from the previous lesson, a complete answer is:

“Let $n$ be the array length. The outer loop chooses the first index, and the inner loop checks every later index. Across all iterations it examines on the order of $n^2$ pairs, so the worst-case time complexity is $O(n^2)$. It uses only loop indices and temporary values, so the auxiliary-space complexity is $O(1)$.”

That explanation is short, precise, and grounded in the actual code.

---

Key takeaways

Complexity analysis is about growth with input size, not stopwatch timing.

• Adjacent loops add; two $O(n)$ loops remain $O(n)$.
• Fully nested loops generally multiply; two full $n$-sized loops give $O(n^2)$.
• Dependent loop bounds often require summing the work, but triangular pair scans are still $O(n^2)$.
• A counter that repeatedly doubles or halves yields $O(\log n)$ iterations.
• Hidden linear operations such as includes, indexOf, or slice can change the complexity of surrounding code.
• Auxiliary space counts extra arrays, maps, sets, and recursion-stack frames, not merely the variables you can see.
• For recursion, total calls determine time; maximum simultaneously active call depth helps determine space.

Next, you will use one of the most valuable trade-offs in interview algorithms: JavaScript Map and Set for expected constant-time lookup, typically exchanging $O(n)$ extra space for a major time improvement.