Structure, Execution, and Analysis of Algorithms using Euclid's Example

Key Insight

Algorithms are presented using a standardized notation to ensure clarity and precision. Each algorithm is assigned an identifying letter, such as 'E' for Euclid's algorithm, with its individual steps numbered (e.g., E1, E2, E3). Every step begins with a bracketed phrase succinctly summarizing its main purpose, followed by a detailed description using words and symbols that outlines the action or decision. Parenthesized comments serve as explanatory information without defining algorithmic actions. The assignment operation, denoted by an arrow (e.g., 'm is set to n'), is fundamentally different from the equality relation ('does m equal n?'), which represents a condition to be tested. The sequence of multiple assignments is critical, as 'm is set to n, n is set to r' yields different results than 'n is set to r, m is set to n'.

Euclid's algorithm, designed to find the greatest common divisor (GCD) of two positive integers 'm' and 'n', provides a clear example of this structure and execution. Its steps are: E1. calculating the remainder 'r' when 'm' is divided by 'n'; E2. checking if 'r' is 0, in which case 'n' is the GCD and the algorithm concludes; and E3. reducing the problem by setting 'm' to 'n' and 'n' to 'r', then looping back to E1. For instance, finding the GCD of 119 and 544 involves several iterations: initially, r=119, then m=544, n=119; next, r=68, then m=119, n=68; subsequently, r=51, then m=68, n=51; then r=17, then m=51, n=17. Finally, when 51 is divided by 17, r=0, terminating the algorithm and confirming 17 as the GCD. An optional initial step, E0, can ensure 'm' is greater than or equal to 'n', potentially reducing execution time by half.

The quantitative study of an algorithm's behavior is known as 'algorithmic analysis', which helps determine performance characteristics like execution time. For Euclid's algorithm, analyzing the average number of times step E1 is performed (T sub n) for a given 'n' and varying 'm' reveals that T sub n is approximately (12 * 0.6931471805599453 / 9.869604401089358) * natural logarithm of n, indicating proportionality to log(n). This analysis averages results for 'm' from 1 to 'n', as only the remainder of 'm' by 'n' is relevant after the initial step. Algorithms can also be formally grounded mathematically as a computational method, defined as a quadruple (Q, I, Omega, f), where 'Q' represents computation states, 'I' inputs, 'Omega' outputs, and 'f' the computational rule. An algorithm, in this formal sense, is a computational method guaranteed to terminate in a finite number of steps for all inputs, aligning with rigorous frameworks like Markov's theory or Turing machines, though 'effectiveness' remains a crucial practical constraint.