Explain where in the construction of an algorithm it is appropriate to use a function

11.3 Structured Programming – Using Functions

Objective

Explain at which stage in the construction of an algorithm it is appropriate to introduce a function, and why this improves the design.

Why Introduce Functions?

• Encapsulation – isolates a specific task.
• Re‑use – the same code can be called from multiple places.
• Readability – high‑level description becomes clearer.
• Testing – individual functions can be unit‑tested in isolation.
• Maintenance – changes to a task need only be made in one location.

When to Use a Function in an Algorithm

A function should be introduced when any of the following conditions are met:

1. Repeated Action: The same sequence of steps occurs more than once.
2. Complex Sub‑task: A part of the algorithm is conceptually distinct and involves several steps.
3. Abstraction Needed: The main flow would be clearer if a sub‑process were hidden behind a name.
4. Parameterisation: The same logic must operate on different data values.
5. Testing Requirement: The sub‑task should be verified independently.

Typical Points in the Development Process to Insert Functions

Example: Computing the Median of a List

Consider an algorithm that must compute the median of several data sets. The steps “sort the list” and “pick the middle element” are repeated for each data set.

Without functions (pseudocode):

READ n
FOR i FROM 1 TO n
READ size
READ size numbers INTO list
// sort list
FOR j FROM 1 TO size-1
FOR k FROM j+1 TO size
IF list[j] > list[k] THEN SWAP list[j], list[k]
END FOR
END FOR
// pick median
IF size MOD 2 = 1 THEN
median ← list[(size+1)/2]
ELSE
median ← (list[size/2] + list[size/2 + 1]) / 2
END IF
OUTPUT median
END FOR

With functions (pseudocode):

FUNCTION sortAscending(list)
FOR j FROM 1 TO LENGTH(list)-1
FOR k FROM j+1 TO LENGTH(list)
IF list[j] > list[k] THEN SWAP list[j], list[k]
END FOR
END FOR
END FUNCTION
FUNCTION median(list)
CALL sortAscending(list)
SET n ← LENGTH(list)
IF n MOD 2 = 1 THEN
RETURN list[(n+1)/2]
ELSE
RETURN (list[n/2] + list[n/2 + 1]) / 2
END IF
END FUNCTION
READ sets
FOR i FROM 1 TO sets
READ size
READ size numbers INTO data
OUTPUT median(data)
END FOR

Notice how the main loop now reads like a high‑level description, while the details of sorting and median extraction are encapsulated in functions.

Mathematical Justification

The benefit can be expressed as a reduction in algorithmic complexity of the main flow:

\$\$

\text{Complexity}{\text{main}} = O(k) \quad\text{vs.}\quad \text{Complexity}{\text{main+functions}} = O(k) + \sum{i=1}^{m} O(fi)

\$\$

where \$k\$ is the number of high‑level steps, \$m\$ the number of functions, and \$f_i\$ the internal complexity of each function. The overall asymptotic order remains unchanged, but readability improves from \$O(k)\$ to \$O(k + m)\$ in terms of cognitive load.

Suggested Diagram

Key Take‑aways

• Introduce functions during the design stage when a task is identifiable as a distinct unit.
• Use them to replace repeated code, to hide complexity, and to enable independent testing.
• Maintain a clear naming convention so that the main algorithm reads like a narrative.