Time Complexity of Three Nested Loops With a Middle Loop That Steps by i

Quick Overview

A complexity analysis question about three nested loops in which the middle loop steps by the outer index and the inner loop steps by two. It asks for the tightest Big-O bound and tests counting the iterations of each loop and recognizing a harmonic series in the total.

Time Complexity of Three Nested Loops With a Middle Loop That Steps by i

Company: BNY Mellon

Role: Software Engineer

Category: Software Engineering Fundamentals

Difficulty: easy

Interview Round: Online Assessment

A multiple-choice question asks for the time complexity of three nested loops. The outer loop runs `i` from 1 to `n`, the middle loop increases `j` by `i` on every iteration, and the inner loop increases `k` by 2 on every iteration. Assume the middle and inner loops both run up to `n`: ```c for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j += i) for (int k = 1; k <= n; k += 2) count++; ``` Give the tightest Big-O bound on the number of times `count++` runs, with a derivation. The answer options were not reported, so state the bound directly. ```hint Fix the outer variable For one fixed value of `i`, count the middle loop's iterations, and notice that the inner loop's count depends on neither `i` nor `j`. ``` ```hint Add up the pieces Write the total as a sum over `i` and look for a series whose growth you know. ``` ### Clarifying Questions - Do the middle and inner loops both run up to `n`, or does either stop at `i` or `j`? - Do the loops start at 0 or at 1, and does that change the answer? - Is the question asking for a tight bound or for any valid upper bound? ### What a Strong Answer Covers - The iteration count of each loop, with the middle loop's count depending on `i` - Recognition of the harmonic sum in the total and its logarithmic growth - A tight bound backed by both an upper and a lower argument, and why rounding does not matter - How the answer changes when a loop bound or step changes ### Follow-up Questions - What is the complexity if the inner loop runs `k` from 1 to `j` instead of to `n`? - What if the middle loop doubles `j` on each iteration instead of adding `i`? - What if the inner loop runs only up to `i`?

Overview: A complexity analysis question about three nested loops in which the middle loop steps by the outer index and the inner loop steps by two. It asks for the tightest Big-O bound and tests counting the iterations of each loop and recognizing a harmonic series in the total.

Read the full BNY Mellon Software Engineer interview experience this question came from

BNY Mellon logo
BNY Mellon
Oct 29, 2026
easySoftware EngineerOnline AssessmentSoftware Engineering Fundamentals
0
0

A multiple-choice question asks for the time complexity of three nested loops. The outer loop runs i from 1 to n, the middle loop increases j by i on every iteration, and the inner loop increases k by 2 on every iteration. Assume the middle and inner loops both run up to n:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        for (int k = 1; k <= n; k += 2)
            count++;

Give the tightest Big-O bound on the number of times count++ runs, with a derivation. The answer options were not reported, so state the bound directly.

Clarifying Questions Guidance

  • Do the middle and inner loops both run up to n , or does either stop at i or j ?
  • Do the loops start at 0 or at 1, and does that change the answer?
  • Is the question asking for a tight bound or for any valid upper bound?

What a Strong Answer Covers Guidance

  • The iteration count of each loop, with the middle loop's count depending on i
  • Recognition of the harmonic sum in the total and its logarithmic growth
  • A tight bound backed by both an upper and a lower argument, and why rounding does not matter
  • How the answer changes when a loop bound or step changes

Follow-up Questions Guidance

  • What is the complexity if the inner loop runs k from 1 to j instead of to n ?
  • What if the middle loop doubles j on each iteration instead of adding i ?
  • What if the inner loop runs only up to i ?