Q.Why is verification of algorithm an important step in problem solving?

Why Bother Verifying an Algorithm?

Imagine you write a recipe for a cake. You follow every step perfectly — flour, eggs, sugar, bake at 180°C for 30 minutes. But the cake comes out raw in the middle. The recipe itself was wrong. You didn't need to debug your cooking; you needed to verify the recipe.

That's the core idea. An algorithm is a recipe — a step-by-step procedure to solve a problem. Algorithm verification is the process of proving, logically and mathematically, that the recipe always does what it claims, for every valid input, before you ever run it.

The Intuition: Two Kinds of Correctness

When you verify an algorithm, you check two things:

1. Partial correctness: If the algorithm ever finishes, is the answer right?
2. Termination: Does the algorithm always finish?

Together, these give total correctness: the algorithm always finishes, and when it does, the answer is correct.

Think of a vending machine. Partial correctness says: "If it gives you a drink, it's the one you paid for." Termination says: "It always gives you a drink — it never gets stuck forever." You need both.

The Precise Statement

Formally, an algorithm is verified using preconditions and postconditions.

• Precondition: What must be true before the algorithm runs (e.g., the input is a positive integer).
• Postcondition: What must be true after the algorithm runs (e.g., the output is the square root of the input, accurate to 0.001).

Verification means proving:

If the precondition holds and the algorithm terminates, then the postcondition holds.

This is done using loop invariants — a statement that remains true before and after each iteration of a loop. If you can prove the invariant holds initially, stays true through every loop, and implies the postcondition when the loop ends, you've proved partial correctness.

Why It Matters

In exams, you'll often be asked to "verify" a simple algorithm — typically a loop that computes a sum, finds a maximum, or searches an array. The skill is not about running the code in your head; it's about writing a clear invariant and proving each step.

For example, consider an algorithm that finds the maximum element in an array $A[1..n]$.

• Precondition: $n \geq 1$, $A$ contains integers. …