Problems, instances and algorithms; correctness; counting basic steps

1 · The Hook

🎣

Two programs sort the same million numbers. One finishes in a second, the other in a day. Faster hardware cannot close that gap; only a better algorithm can. To compare algorithms we need a way of measuring them that does not depend on the computer: count the basic steps they take. That counting is the core skill of this whole subject.

2 · Predict First

🤔

This loop runs on an array of n numbers. How many times does the line s = s + A[i] execute?

s = 0;
for (i = 0; i < n; i++)
    s = s + A[i];

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

3 · Core Concept

💡

Predict First — the answer

Exactly n times, once for each i from 0 to n − 1. (The test i < n runs n + 1 times: the last test fails and ends the loop.)

Problems, instances, algorithms

• A problem states what the input is and what the output must be. Sorting: input a list of numbers; output the same numbers in ascending order.
• An instance is one particular input: [5, 2, 9, 1, 7, 3].
• An algorithm is a finite sequence of precise steps that solves every instance of the problem: it must take input, produce output, use only well-defined (unambiguous) and doable steps, and finish after finitely many steps.

Correctness

An algorithm is correct if, for every instance, it stops and gives the right output. One failing instance makes it incorrect. A common proof tool is a loop invariant: a statement true before every iteration (for the loop above: "s equals the sum of A[0..i−1]"); when the loop ends (i = n), the invariant says s is the total.

Counting steps (the RAM model)

We pretend the computer does each basic operation in one unit of time: an arithmetic operation, a comparison, an assignment, reading or writing one array element, following one pointer. Then:

• Running time T(n) = the number of basic steps for an input of size n (number of elements, number of bits, number of vertices …).
• We care most about how T(n) grows as n grows (Phase 1).

Counting statement executions

Count how many times the loop body runs:

4 · Visual

Problem  : "sort a list"                      (what)
Instance : [5, 2, 9, 1, 7, 3]                 (one input)
Algorithm: insertion sort, merge sort, ...    (how; must work for EVERY instance)

Cost model: 1 step per basic operation  ->  T(n) = steps as a function of input size n

5 · Worked Examples

Example 1 Easy

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

Solution

i = 3, 6, …, 30: 10 times.

Example 2 Medium

How many times does x = x + 1 run?

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

Solution

The inner loop runs 5 times for each of the n values of i: 5n.

Example 3 GATE

An algorithm returns the right answer on every input of size up to 1,000, but loops forever on one input of size 1,001. Is it correct?

Solution

No. A correct algorithm must stop with the right output on every instance.

6 · GATE Traps

⚠️

• The loop test runs one more time than the body.
• Step counts depend on the input size, so always say what n is.
• "Works on the examples" is not correctness: every instance must work.
• Stepping by 2 halves the count; multiplying by 2 gives a logarithm.

7 · Memory Hook

🧠

"Problem = what, instance = which, algorithm = how, for all."

8 · Connect the Dots

This lesson fixed the unit: steps as a function of n. Next: the math toolkit (logs, floors and ceilings, sums) that turns loops into formulas.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markLoop count

How many times does the body of for (i = 0; i < 100; i += 4) run?

Numerical answer: ________

Q2NAT1 markNested count

How many times does the innermost statement run?

for (i = 0; i < 20; i++)
    for (j = 0; j < 30; j++)
        count++;

Numerical answer: ________

Q3MCQ1 markCorrectness

An algorithm is correct if:

• (A) it halts with the right output on every valid input
• (B) it never uses more than n² steps
• (C) it gives the right answer on most inputs
• (D) it runs in polynomial time

Q4NAT1 markTest count

In for (i = 1; i <= n; i++), how many times is the test i <= n evaluated when n = 10?

Numerical answer: ________

Q5MSQ2 marksTerms

Which are true?

• (A) An algorithm may run forever on some inputs and still be correct.
• (B) Running time is measured as a function of input size.
• (C) In the RAM model, comparing two numbers costs one step.
• (D) An instance is one specific input of a problem.

10 · Rule Card

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

11 · Concept Ledger

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

probleminstancealgorithmcorrectnessloop invariantRAM modelbasic stepinput size nrunning time T(n)

12 · Answer Vault