Reading Pseudocode & Predicting Output

Last lesson asked you to be the machine for a recursive function — to follow each call without guessing. This lesson widens that same discipline to every loop GATE can throw at you, and adds the one tool that makes it reliable. GATE sometimes writes algorithm questions in language-neutral pseudocode — a plain sketch of an algorithm, tied to no one language: arrays indexed from 1, loops written for i = 1 to n, an explicit swap. There is no trick and nothing to memorise; the only skill is careful, patient tracing.

The students who lose marks are the ones who trace in their head; the students who score keep a table. It is also the exact habit that lets you debug a misbehaving loop in real code — step it by hand and watch the variables move, one row at a time.

Trace with a table — one row per iteration

The single technique for this whole topic: write down each variable and update its value on every pass. Take this loop (1-indexed, bound inclusive):

x = 0
for i = 1 to 4:
    x = x + i

Maintain a small table — the variable’s value after each iteration:

The loop runs for i = 1, 2, 3, 4 (the bound 4 is inclusive), accumulating 1 + 2 + 3 + 4 = 10. The table makes that impossible to get wrong — every value is written down, so nothing is held in a slippery mental register.

Nested loops — count the inner iterations

When one loop sits inside another, the inner bound often depends on the outer variable. Trace the outer loop, and for each outer value count how many times the inner body runs:

count = 0
for i = 1 to 3:
    for j = 1 to i:      # inner bound depends on i
        count = count + 1

• i = 1: inner runs for j = 1 → 1 time
• i = 2: inner runs for j = 1, 2 → 2 times
• i = 3: inner runs for j = 1, 2, 3 → 3 times

Total count = 1 + 2 + 3 = 6. (A square nest like for j = 1 to 3 inside for i = 1 to 3 would instead give 3 × 3 = 9 — read the inner bound carefully, because that one difference is the whole answer.)

# Pseudocode 'for i = 1 to n' is inclusive; range(1, n+1) matches it.
x = 0
for i in range(1, 5):          # i = 1,2,3,4
    x = x + i
print("x =", x)

count = 0
for i in range(1, 4):          # i = 1,2,3
    for j in range(1, i + 1):  # j = 1..i
        count += 1
print("count =", count)

prints:

x = 10
count = 6

The triangular nest gives 6, not 9 — the inner bound j = 1 to i runs fewer times than a fixed j = 1 to 3 would.

Array-mutation loops — write the array after each step

When a loop mutates an array, keep the whole array in your table. Here is a single bubble-style pass over a 1-indexed array A:

A = [5, 3, 8, 1]              # A[1]=5, A[2]=3, A[3]=8, A[4]=1
for i = 1 to 3:
    if A[i] > A[i+1]:
        swap A[i], A[i+1]

• i = 1: A[1]=5 > A[2]=3 → swap → [3, 5, 8, 1]
• i = 2: A[2]=5 > A[3]=8? no → unchanged [3, 5, 8, 1]
• i = 3: A[3]=8 > A[4]=1 → swap → [3, 5, 1, 8]

The largest element has “bubbled” one step right. Tracking the full array after each pass is the only way to stay correct — a remembered array is a wrong array.

How GATE asks this

GATE DA 2024 included a predict-the-output item written in pseudocode: a loop with an accumulator and a conditional, where you trace to a single final value (MCQ) or enter it (NAT). The setup varies — sums, counters, a swap inside an array loop — but the method never does: build the trace table and read off the last row.

A question to carry forward

Look back at that nested loop. You counted its body running exactly 6 times for n = 3, and 9 for the square version — precise numbers, carefully traced. But now imagine n is not 3 but a million. Nobody traces a million rows, and the exact count stops being the point. What matters then is the shape of the growth: a single loop to n does about n steps, while that square nest does about n² — and n² for a million is a trillion. Here is the thread onward: how do we describe and compare how an algorithm’s work grows with the input size, ignoring the exact count but capturing whether it scales like n, like n², or like log n?

In one breath

• GATE pseudocode is language-neutral: 1-indexed arrays, for i = 1 to n (inclusive), explicit swap. The only skill is patient tracing.
• Keep a trace table: one row per iteration, every variable’s value written down — never trace in your head.
• Nested loop with inner bound 1 to i is triangular: 1+2+3 = 6 for n=3 (not 3×3 = 9).
• Array-mutation loop: write the whole array after each pass (a bubble pass floats the max to the end).
• Off-by-one is the killer: 1-indexed vs 0-indexed, inclusive to n vs Python range(1,n), and reading A[i+1] past the end.

Practice