Efficient pseudocode — doing less work for the same answer

Two programs can be correct and still be very different.

One finds a name in a list of 500 after 4 comparisons. The other makes 500 comparisons. Both print the right answer. One of them is finished before the other has warmed up.

Efficient pseudocode reaches the same result using fewer operations. That is the whole idea, and it is what 11.3.7 asks you to write.

It does not mean fewer lines. You can make a program shorter by cramming three things onto one line and make it slower at the same time. Examiners reward the algorithm that does less, not the one that looks tidiest.

Four habits do most of the work: don't calculate the same thing twice, don't recalculate inside a loop what does not change, stop as soon as you know the answer, and reuse subprograms instead of copying them.

If a value is needed in two places, work it out once and keep it in a variable.

// wasteful: the area is calculated twice
IF (Base * Height) / 2 > 100 THEN
  OUTPUT (Base * Height) / 2
ENDIF

// efficient: calculated once, used twice
Area ← (Base * Height) / 2
IF Area > 100 THEN
  OUTPUT Area
ENDIF

Both print the same number when the area is over 100.

The second does one multiplication, one division and one comparison. The first does two multiplications, two divisions and one comparison.

Notice what has not changed: the answer. Efficiency is never a reason to change what the program outputs — only how much work it does to get there.

A loop runs its body many times, so anything inside it is paid for on every pass. Anything that does not depend on the loop counter belongs outside.

// wasteful: Average is recalculated 500 times
FOR Index ← 1 TO 500
  IF Score[Index] > Average(Scores) THEN
    OUTPUT Name[Index]
  ENDIF
NEXT Index

// efficient: calculated once, before the loop
Mean ← Average(Scores)
FOR Index ← 1 TO 500
  IF Score[Index] > Mean THEN
    OUTPUT Name[Index]
  ENDIF
NEXT Index

Average(Scores) never changes while the loop runs — Scores is not being edited — so the second version calls it once instead of 500 times.

This is the single most common efficiency mark in 9618 answers. If you can point at an expression inside a loop and say "this does not depend on the counter", move it out.

A search that keeps looking after it has found the target is doing pointless work.

FUNCTION FindName(Target : STRING) RETURNS INTEGER
  DECLARE Index : INTEGER
  DECLARE Found : BOOLEAN

  Index ← 1
  Found ← FALSE

  WHILE Index <= 500 AND NOT Found
    IF Name[Index] = Target THEN
      Found ← TRUE
    ELSE
      Index ← Index + 1
    ENDIF
  ENDWHILE

  IF Found THEN
    RETURN Index          // position of the match
  ELSE
    RETURN -1             // not in the list
  ENDIF
ENDFUNCTION

The WHILE condition does two jobs at once. It stops when Index runs past the end of the list, and it stops the moment the target has been found — once Found becomes TRUE, Index is no longer increased. If the target is at position 4, the loop body runs 4 times and then quits — not 500.

Notice that the comparison Name[Index] is inside the body, not in the condition. The body only runs while Index <= 500, so the algorithm never reads beyond the end of the array.

That is why WHILE is often the right loop for a search. A FOR Index ← 1 TO 500 loop runs all 500 passes no matter what it finds, because the counter decides when a FOR ends.

The same idea applies to validation: if the first check fails, there is no need to run the remaining four checks on data you already know is bad.

Reuse. If the same block of statements is needed three times, write it once as a procedure and call it three times. The program then contains one copy to maintain instead of three, which is what makes it easier to change without breaking.

Be precise about what this buys you: the statements still run on each call, so the running time does not fall. What falls is the amount of code written and the number of places a change has to be made.

Nesting. A loop inside a loop multiplies the work. 100 passes of an outer loop each running 100 passes of an inner loop is 10 000 trips through the inner body.

Before writing a nested loop, ask whether two separate loops would do. Two loops of 100 is 200 passes — one fiftieth of the work, same answer.

Sorting. Sorting 500 items to find the largest one is wasted effort: one pass comparing each item with the best so far finds it in 500 comparisons, where sorting takes far more.