What an algorithm is

ACompressed recap

🧾

Problem, instance, algorithm (finite, precise, works for every instance); correct = halts with the right output always; loop invariants. RAM model: one step per basic operation; T(n) as a function of input size. Loop counts: step k from a to b → ⌊(b − a)/k⌋ + 1; nested loops multiply; doubling or halving loops → about log n. Logs: change of base, a^(log n) = n^(log a); sums: n(n+1)/2, n(n+1)(2n+1)/6, 2ᵏ⁺¹ − 1, Hₙ ≈ ln n, log n! ≈ n log n.

BMerged rule card

0.1.1 Problems, instances and algorithms; correctness; counting basic steps

• Problem (what), instance (one input), algorithm (finite precise steps for all instances).
• Correct = halts with correct output on every instance; loop invariants prove it.
• RAM model: each basic operation = 1 step; T(n) = steps for input size n.
• Loop counts: step k from a to b → ⌊(b − a)/k⌋ + 1 runs; nested loops multiply.

0.1.2 Math toolkit: logarithms, floors and ceilings, sums (arithmetic, geometric, harmonic)

• log = log₂; bases differ by constants; a^(log_b n) = n^(log_b a).
• Halving to 1: ⌊log n⌋ steps; n has ⌊log n⌋ + 1 bits; doubling to ≥ n: ⌈log n⌉.
• Σi = n(n+1)/2; Σi² = n(n+1)(2n+1)/6; Σ2ⁱ (0..k) = 2ᵏ⁺¹ − 1; Hₙ ≈ ln n; log n! ≈ n log n.
• Decreasing geometric series: constant.

CInterleaved GATE-style questions

Q1NAT1 markLoop

How many times does the body of for (i = 5; i <= 95; i += 5) run?

Numerical answer: ________

Q2NAT2 marksNested loop

How many times does c++ run?

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

for n = 10?

Numerical answer: ________

Q3NAT1 markLog

log₂(4096) = ?

Numerical answer: ________

Q4NAT2 marksSum of squares

1² + 2² + … + 10² = ?

Numerical answer: ________

Q5NAT2 marksHalving loop

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

for (i = n; i >= 1; i = i / 3)
    count++;

Numerical answer: ________

Q6MCQ1 markSwap rule

2^(2 log n) equals:

• (A) n log n
• (B) 2n
• (C) 4n
• (D) n²

Q7MSQ2 marksDefinitions

Which are required of an algorithm?

• (A) It runs in linear time.
• (B) It produces output.
• (C) It terminates after finitely many steps on every input.
• (D) Each step is precisely defined.

Q8NAT1 markGeometric

1 + 2 + 4 + … + 512 = ?

Numerical answer: ________

DAnswer Vault