Write efficient pseudocode

11.3 Structured Programming

Objective

Develop the ability to write clear, maintainable and efficient pseudocode that follows the principles of structured programming.

1. What is Structured Programming?

Structured programming is a programming paradigm that promotes the use of a limited set of control structures – sequence, selection and iteration – to produce programs that are easier to understand, test and modify. It discourages the use of goto statements and encourages a top‑down design approach.

2. Core Principles

• Single‑entry, single‑exit – each block of code (e.g., a loop or sub‑routine) should have one entry point and one exit point.
• Modularity – break the problem into smaller, self‑contained modules (functions/procedures).
• Hierarchy – organise modules in a logical hierarchy, from high‑level control flow down to low‑level details.
• Readability – use meaningful identifiers, consistent indentation and comments.
• Efficiency – choose algorithms and data structures that minimise time and space complexity.

3. Writing Efficient Pseudocode

Efficiency in pseudocode is about expressing the algorithm in a way that highlights its computational cost and avoids unnecessary operations. Follow these guidelines:

1. Identify the most expensive operations (usually loops, nested loops, and recursive calls).
2. Use appropriate data structures (arrays, lists, dictionaries) that give the best average‑case performance for the required operations.
3. Prefer while loops or for loops with a known bound over indefinite loops.
4. Eliminate redundant calculations by storing intermediate results.
5. Apply algorithmic analysis (Big‑O notation) to each part of the pseudocode.

4. Control Structures

The three fundamental control structures are shown in the table below.

statement1
statement2
statement3

IF condition THEN
statements
ELSE
statements
ENDIF

FOR i FROM 1 TO n DO
statements
ENDFOR
WHILE condition DO
statements
ENDWHILE

5. Modular Design

Break the solution into procedures or functions. Each module should have a single, well‑defined purpose.

• Procedure header – name, input parameters, output parameters.
• Local variables – declared at the start of the module.
• Comments – brief description of what the module does.

6. Example: Finding the Second Largest Number in a List

This example demonstrates a linear‑time algorithm (\$O(n)\$) written in efficient pseudocode.

PROCEDURE FindSecondLargest(list)
// Pre‑condition: list contains at least two distinct numbers
max ← list[1]
secondMax ← -∞
FOR i FROM 2 TO LENGTH(list) DO
IF list[i] > max THEN
secondMax ← max
max ← list[i]
ELSE IF list[i] > secondMax AND list[i] ≠ max THEN
secondMax ← list[i]
ENDIF
ENDFOR
RETURN secondMax
ENDPROCEDURE

Analysis:

• Each element is examined exactly once – time complexity \$O(n)\$.
• Only a constant amount of extra storage is used – space complexity \$O(1)\$.
• No nested loops or recursion, satisfying the single‑entry, single‑exit rule for the loop.

7. Common Pitfalls and How to Avoid Them

• Unnecessary nested loops – often can be replaced by a single pass with auxiliary variables.
• Repeated calculations inside loops – move invariant calculations outside the loop.
• Using global variables excessively – prefer passing parameters to maintain modularity.
• Missing termination condition – always ensure loops have a clear exit condition.

8. Summary Checklist

1. Have I used only sequence, selection and iteration?
2. Does each loop have a single, well‑defined exit condition?
3. Are modules small, with clear input and output?
4. Have I identified and minimised the most costly operations?
5. Is the algorithm’s time and space complexity stated?

9. Self‑Assessment Questions

1. Write pseudocode to compute the factorial of a non‑negative integer using a for loop. State its time complexity.
2. Explain why the following pseudocode is inefficient and rewrite it to improve efficiency:

   FOR i FROM 1 TO n DO
   FOR j FROM 1 TO i DO
   sum ← sum + array[j]
   ENDFOR
   ENDFOR
   

3. Given a list of \$n\$ numbers, describe a structured‑programming approach to determine whether the list is sorted in ascending order. Provide the pseudocode and its complexity.