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.
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
?