What Is an Algorithm Formula? An Algorithm Is a Procedure, Not a Formula

There is no single "algorithm formula". An algorithm is a procedure, a finite list of steps, while a formula is one expression that gives a value. The two are related. A formula is often one step inside an algorithm, and an algorithm can wrap a formula in the checks and repeats that a formula cannot express. When students search for the formula of an algorithm they usually want one of three things: the definition of an algorithm, a way to write an algorithm down, or a math formula turned into steps. This page answers all three.

Algorithm vs Formula

A formula is a fixed relationship between values. The area of a circle is pi times r squared. You substitute a value for r and you get one answer in one step. There is no branching and no repetition.

An algorithm is a finite sequence of unambiguous steps that turns an input into an output. It can test a condition, repeat a step, and stop early. Long division is an algorithm. Sorting a list of names is an algorithm. Neither one fits in a single expression.

So "is an algorithm a formula" has a clear answer: no. A formula can be part of an algorithm, and every formula can be turned into a short algorithm, but the reverse is not true.

How a Formula Becomes an Algorithm

The quadratic formula is the standard example. The formula gives the roots of ax^2 + bx + c = 0 as x = (-b +- sqrt(b^2 - 4ac)) / 2a. As a formula it is one line. As soon as a program has to use it, three questions appear that the formula does not answer. What if a is zero? What if the discriminant b^2 - 4ac is negative? Should the program return one root or two?

Answering those questions turns the formula into an algorithm.

Algorithm SolveQuadratic
Input: real numbers a, b, c
Output: the real roots, or a message

1. If a = 0, stop and report "not quadratic".
2. Set d = b*b - 4*a*c.
3. If d < 0, stop and report "no real roots".
4. If d = 0, return -b / (2*a) as the only root.
5. Otherwise return (-b + sqrt(d)) / (2*a) and (-b - sqrt(d)) / (2*a).

The formula is step 5. Steps 1 to 4 are the parts a formula cannot hold: an input check, a decision, and an early stop. This is the general pattern. Whenever a formula is applied to real data, the programmer has to add steps around it, and the result is an algorithm.

The Parts of an Algorithm

Every algorithm, however it is written, has the same five parts. Knuth's list is the one textbooks use.

• Input. Zero or more values supplied before the steps start.
• Output. At least one value produced at the end.
• Definiteness. Each step is exact, with only one possible meaning.
• Finiteness. The steps end after a finite number of operations for every valid input.
• Effectiveness. Each step is basic enough to be carried out exactly, by hand if needed.

Two Ways to Represent an Algorithm

The two methods that schools teach are pseudocode and flowcharts. Code is the third, and it is the one that actually runs.

Pseudocode is plain language laid out like a program. It uses words such as if, for each, and return, but it does not follow the syntax of any one language. The SolveQuadratic listing above is pseudocode.

A flowchart draws the same steps as boxes joined by arrows. An oval marks start and end, a rectangle marks an action, a diamond marks a decision, and a parallelogram marks input or output. For SolveQuadratic the chart has one start oval, two diamonds (a = 0? and d < 0?), and three end ovals.

Code is the algorithm in a real language. Here is the same algorithm in Python:

import math

def solve_quadratic(a, b, c):
    if a == 0:
        return "not quadratic"
    d = b * b - 4 * a * c
    if d < 0:
        return "no real roots"
    if d == 0:
        return (-b / (2 * a),)
    root = math.sqrt(d)
    return ((-b + root) / (2 * a), (-b - root) / (2 * a))

print(solve_quadratic(1, -3, 2))   # (2.0, 1.0)
print(solve_quadratic(1, 2, 5))    # no real roots

Formulas That Describe Algorithms

There is one place where a formula does belong next to an algorithm: describing its cost. A recurrence relation is an equation that states the running time of a recursive algorithm in terms of smaller inputs. Merge sort has T(n) = 2T(n/2) + n, which solves to O(n log n). Big O notation itself is a formula-like summary of how running time grows with input size.

These formulas describe an algorithm. They are not the algorithm. If a student asks for "the formula of an algorithm", the honest answer is the list of steps, and then, if needed, the recurrence that measures those steps.