1.1.3 Analysing loops: nested, dependent and logarithmic loops

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Order n^(3/2), n log n, n^(log n), 2ⁿ. from Lesson 1.1.2
Definition of f = O(g)? from Lesson 1.1.1
Σ log i for i = 1..n = ? from Lesson 0.1.2

1 · The Hook

🎣

Most GATE complexity questions are three lines of nested loops. The inner loop might run n times, or i times, or log i times, or n/i times, and each pattern sums to a different growth rate. Learn the five patterns and you can read the complexity off the code.

2 · Predict First

🤔

How many times does x++ run, in Θ terms?

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j += i)
        x++;

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

For each i, the inner loop runs about n/i times. Total ≈ n(1 + 1/2 + 1/3 + … + 1/n) = n·Hₙ = Θ(n log n) (Lesson 0.1.2).

The five loop patterns

Inner loop for each outer i	Total over i = 1..n	Growth
runs n times (independent)	n·n	Θ(n²)
runs i times (j = 1..i)	n(n + 1)/2	Θ(n²)
runs log i times (j doubles up to i)	Σ log i = log n!	Θ(n log n)
runs n/i times (j += i)	n·Hₙ	Θ(n log n)
runs log n times (j doubles up to n)	n log n	Θ(n log n)

Single loops

i = i * 2 or i = i / 2: Θ(log n) iterations.
i = i * i (from 2): 2, 4, 16, 256 …: Θ(log log n).
while (i * i <= n) i++: Θ(√n).

Outer loop that doubles

for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++): inner runs 1 + 2 + 4 + … < 2n: Θ(n), not n log n.

Three loops

for i in n/2..n, for j doubling to n, for k doubling to n: (n/2) × log n × log n = Θ(n log² n).
for i < n, for j < i, for k < j: Σ_{i} Σ_{j<i} j = C(n, 3) = Θ(n³).

Exact counts

GATE sometimes asks the exact number for a given n. Count term by term. For the predict loop with n = 8: inner counts 8, 4, 3, 2, 2, 2, 2, 1 → 24.

4 · Visual

for i = 1..n:  for j = 1..i        for i = 1..n:  for j = 1..n step i
  i=1:  *                            i=1: * * * * * * * *   (n)
  i=2:  * *                          i=2: *   *   *   *      (n/2)
  i=3:  * * *                        i=3: *     *     *      (n/3)
  ...   triangle: n^2 / 2            ...  harmonic: n * H_n = n log n

5 · Worked Examples

Example 1 Easy

Θ of the count?

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;

Solution

n(n + 1)/2 = Θ(n²).

Example 2 Medium

Θ of the count?

for (i = n / 2; i <= n; i++)
    for (j = 1; j <= n; j = 2 * j)
        for (k = 1; k <= n; k = k * 2)
            x++;

Solution

(n/2 + 1) × (log n + 1)² = Θ(n log² n).

Example 3 GATE

Exact count for n = 16?

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j = j * 2)
        x++;

Solution

Inner count = ⌊log i⌋ + 1: i = 1 → 1; 2–3 → 2 each; 4–7 → 3 each; 8–15 → 4 each; 16 → 5. Total 1 + 4 + 12 + 32 + 5 = 54.

6 · GATE Traps

⚠️

A doubling outer loop with an inner loop up to i gives Θ(n), not n log n.
j += i gives n/i iterations → harmonic → n log n.
i = i * i is log log n.
For exact counts, include the first and last values: j = 1, 2, 4, … ≤ i is ⌊log i⌋ + 1 values.

7 · Memory Hook

🧠

"Triangle n², harmonic n log n, doubling inside log, doubling outside linear."

8 · Connect the Dots

Chapter 1.1 is complete: notation, ordering and loops. Chapter 1.2 handles the other source of running times, recursion, where the count is a recurrence.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markHarmonic loop

Θ of the count?

for (i = 1; i <= n; i++)
    for (j = i; j <= n; j += i)
        x++;

(A) Θ(n)
(B) Θ(n log n)
(C) Θ(log n)
(D) Θ(n²)

Q2NAT2 marksExact count

Exact number of times x++ runs for n = 10?

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j += i)
        x++;

Numerical answer: ________

Q3MCQ1 markDoubling outer

Θ of the count?

for (i = 1; i < n; i = i * 2)
    for (j = 0; j < i; j++)
        x++;

(A) Θ(n log n)
(B) Θ(n²)
(C) Θ(log n)
(D) Θ(n)

Q4NAT2 marksTriple loop

Exact count of x++ for n = 10?

for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        for (k = 0; k < j; k++)
            x++;

Numerical answer: ________

Q5NAT1 markSquare-root loop

How many times does the body run for n = 100?

i = 1;
while (i * i <= n) i++;

Numerical answer: ________

10 · Rule Card

Inner i → n²/2; inner log i → n log n; inner n/i → n log n; inner log n → n log n.
Doubling single loop log n; squaring log log n; i² ≤ n → √n.
Doubling outer loop with inner up to i → Θ(n).
i < j < k triple loop → C(n, 3) = Θ(n³).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

independent nested loopsdependent (triangular) loopslogarithmic loopsharmonic loopsgeometric (doubling outer) loopslog log n loops√n loopsexact loop counts

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

n log n < n^(3/2) < n^(log n) < 2ⁿ.
f(n) ≤ c·g(n) for all n ≥ n₀, some c > 0.
log n! = Θ(n log n).