Subalgorithms

A subalgorithm is a self-contained algorithm that is invoked as a component of a larger algorithm to perform a specific subtask. It has a well-defined input and output, a termination condition, and a measurable time and space complexity. In many texts, subalgorithms are treated as building blocks or modules, similar to subroutines or procedures in programming, but with an emphasis on algorithmic structure rather than implementation details.

Subalgorithms support modular design, allowing abstraction and reuse. A larger algorithm may call a subalgorithm multiple times with varying parameters; the overall complexity is analyzed by aggregating the costs of subalgorithm calls. Subalgorithms should have clear interfaces, be logically correct, and ideally be reusable across different algorithms.

Examples include: in graph algorithms, BFS or DFS are common subalgorithms used for traversal inside more complex routines; in shortest-path algorithms, the relaxation operation is a subalgorithm that updates tentative distances; in divide-and-conquer, the conquer step can be treated as a subalgorithm. In dynamic programming, the recurrence often relies on subalgorithm calls to compute subproblems.

Theoretical and practical considerations: the concept helps in formal analysis by isolating subproblems and clarifying dependencies. Practitioners must consider side effects, state, and purity, as well as how subalgorithm boundaries affect caching, memoization, and parallelization. Subalgorithms may be designed to be deterministic or to satisfy certain invariants that facilitate correct composition within the larger algorithm.