A Process Can Be a Mathematical Object
Consider the instruction:
“Given a number, double it and add three.”
If the input is
\[ x, \]then the output is
\[ 2x+3. \]We can represent this same process as a formula:
\[ f(x)=2x+3, \]or as a sequence of steps:
- Input \(x\).
- Multiply \(x\) by \(2\).
- Add \(3\).
- Return the result.
The formula emphasizes the relationship. The algorithm emphasizes the procedure.
\[ \boxed{ \text{algorithm} = \text{precise representation of a process} } \]What Is a Procedure?
A procedure is an ordered method for carrying out a task.
Procedures appear everywhere:
- solving an equation,
- converting units,
- finding a greatest common divisor,
- sorting a list,
- following a recipe,
- checking whether a measurement lies within tolerance.
A procedure may be informal or formal.
For example:
“Keep subtracting \(7\) until the result is less than \(7\).”
This is already procedural, though it can be made more precise.
What Is an Algorithm?
An algorithm is a finite, well-defined procedure for transforming input into output or accomplishing a specified task.
A useful algorithm usually has:
Input
The information the procedure begins with.
Steps
The operations and decisions carried out in order.
Output
The result produced by the procedure.
Stopping Condition
A rule determining when the procedure is finished.
Not every informal procedure is automatically a good algorithm. The steps must be sufficiently clear to execute consistently.
Inputs and Outputs
An algorithm may take one input, several inputs, or no external input at all.
Single Input
Input \(x\), output
\[ x^2. \]Two Inputs
Input \(a\) and \(b\), output
\[ a+b. \]Structured Input
Input a list such as
\[ (8,3,5,1), \]and output the sorted list
\[ (1,3,5,8). \]The type and meaning of the input matter just as they do for functions.
Ordered Steps
The order of algorithmic steps can change the result.
Compare:
- Multiply \(x\) by \(2\).
- Add \(3\).
with:
- Add \(3\) to \(x\).
- Multiply by \(2\).
The first produces
\[ 2x+3, \]while the second produces
\[ 2(x+3)=2x+6. \]Sequence is part of the algorithm's meaning.
Precision and Unambiguity
An algorithm should make each step sufficiently precise that it can be carried out consistently.
An instruction such as
“Make the number reasonably small.”
is ambiguous.
A more precise instruction is:
“While the number is at least \(10\), divide it by \(10\).”
The second version gives a definite condition and operation.
\[ \boxed{ \text{good algorithmic instruction} = \text{clear action + clear condition} } \]Deterministic Procedures
A deterministic algorithm produces the same next step and same output whenever it is given the same input and begins in the same state.
For example:
\[ x\mapsto2x+3 \]is deterministic.
Input
\[ 5 \]always produces
\[ 13. \]Some algorithms can deliberately use randomness, but deterministic algorithms are the simplest starting point for understanding computational structure.
Branching and Decisions
Algorithms can choose different paths depending on a condition.
Example: Absolute Value
Given \(x\):
- If \(x\geq0\), return \(x\).
- Otherwise, return \(-x\).
This corresponds to the piecewise function
\[ |x|= \begin{cases} x,&x\geq0,\\ -x,&x<0. \end{cases} \]Branching introduces logic into a procedure.
A Simple Algorithmic Flow
Iteration and Repetition
An algorithm can repeat a step until a condition is satisfied.
This is called iteration.
Example
Start with
\[ n=20. \]Repeatedly subtract \(3\) while
\[ n\geq3. \]The values are
\[ 20,\ 17,\ 14,\ 11,\ 8,\ 5,\ 2. \]The algorithm stops when the condition \(n\geq3\) becomes false.
Iteration connects algorithms naturally to sequences and recursive rules.
Termination
A finite algorithm must eventually stop for every input in the intended domain.
Consider:
- Start with positive integer \(n\).
- While \(n>0\), replace \(n\) with \(n-1\).
- Stop when \(n=0\).
The value decreases by \(1\) each time, so the algorithm must terminate after finitely many steps.
By contrast, the instruction
“Keep adding \(1\) forever.”
does not terminate.
Termination is a structural property of an algorithm.
Correctness
An algorithm is correct if it produces the intended output for every valid input.
Testing several examples is useful, but examples alone do not always prove correctness.
Example
Suppose an algorithm claims to find the larger of two numbers:
- Input \(a,b\).
- If \(a>b\), return \(a\).
- Otherwise, return \(b\).
If \(a>b\), it returns \(a\), the larger value.
If \(a\leq b\), it returns \(b\), which is at least as large as \(a\).
The logic covers all possible orderings.
Efficiency
Two algorithms can both be correct while requiring very different amounts of work.
Example
To compute
\[ 2^{20}, \]one approach multiplies \(2\) by itself nineteen times.
Another approach can reuse intermediate squares:
\[ 2^2=4, \] \[ 2^4=16, \] \[ 2^8=256, \] \[ 2^{16}=65536, \]then multiply
\[ 2^{16}\cdot2^4=2^{20}. \]The second method uses the structure of exponentiation to reduce repeated work.
Efficiency asks not only whether a procedure works, but how much time, memory, or effort it requires.
Ways to Represent an Algorithm
Algorithms can be represented in several forms.
| Representation | Strength |
|---|---|
| Natural language | Readable and intuitive |
| Numbered steps | Clear sequence |
| Pseudocode | Precise without depending on one programming language |
| Flowchart | Visualizes branching and flow |
| Formula | Compact for direct mathematical mappings |
| Program code | Executable by a computer |
The algorithm is the underlying procedure; these are different representations of it.
Algorithms and Functions
Many deterministic algorithms behave like functions:
\[ \text{input} \longmapsto \text{output}. \]For example, the algorithm
- Input \(x\).
- Square \(x\).
- Add \(1\).
- Return the result.
computes
\[ f(x)=x^2+1. \]But algorithms can also do more than evaluate a simple formula. They can:
- branch,
- repeat steps,
- process lists or matrices,
- search, sort, compare, and update data,
- maintain intermediate state.
Algorithms in Mathematics
Mathematics has used algorithms long before electronic computers.
Examples include:
- long addition and subtraction,
- long multiplication and division,
- Euclid's algorithm for greatest common divisors,
- root-finding procedures,
- row reduction,
- synthetic division,
- numerical approximation methods.
A written mathematical method is often an algorithm even when no computer is involved.
Practical Applications
Software
Programs implement algorithms for processing input and producing output.
Spreadsheets
Formulas and repeated operations encode procedures over rows, columns, and data sets.
Engineering
Algorithms control simulations, optimization, numerical methods, and automated systems.
Business
Procedures govern pricing, scheduling, forecasting, inventory, and financial calculations.
Everyday Problem Solving
A reliable checklist or repeatable method is algorithmic thinking even when no computer is present.
Worked Examples
Example 1: Translate a Formula into Steps
Given
\[ f(x)=3x-4, \]an algorithm is:
- Input \(x\).
- Multiply by \(3\).
- Subtract \(4\).
- Return the result.
Example 2: Branch on Sign
Create an algorithm returning \(1\) for nonnegative input and \(-1\) for negative input.
- Input \(x\).
- If \(x\geq0\), return \(1\).
- Otherwise, return \(-1\).
Example 3: Repeated Addition
To compute
\[ 5(7), \]one algorithm is:
- Set total \(=0\).
- Repeat five times: add \(7\) to total.
- Return total.
The output is
\[ \boxed{35}. \]Example 4: Find the Maximum of Three Values
Input \(a,b,c\).
- Set \(m=a\).
- If \(b>m\), set \(m=b\).
- If \(c>m\), set \(m=c\).
- Return \(m\).
The variable \(m\) stores the largest value found so far.
Example 5: Terminating Loop
Input positive integer \(n\).
- While \(n>1\), replace \(n\) with \(n-1\).
- Return \(n\).
The algorithm terminates because \(n\) decreases by \(1\) and cannot remain above \(1\) forever.
Example 6: Algorithm versus Formula
The rule
\[ a_{n+1}=2a_n, \qquad a_0=1 \]can be read algorithmically:
- Start with \(a=1\).
- Replace \(a\) with \(2a\).
- Repeat as many times as required.
This generates
\[ 1,\ 2,\ 4,\ 8,\ 16,\ldots \]and connects recursion, sequences, and iteration.
Common Errors
1. Writing Steps That Depend on Unstated Judgment
Instructions such as “make it small enough” need a precise criterion.
2. Forgetting Input Restrictions
An algorithm that divides by \(x\) must account for the case \(x=0\).
3. Ignoring Step Order
Changing operation order can change the output.
4. Creating a Loop with No Guaranteed Stopping Condition
Repetition must be paired with a condition that can eventually become false.
5. Confusing Correctness with Efficiency
An inefficient algorithm can still be correct, and a fast algorithm can still be wrong.
6. Treating the Representation as the Algorithm Itself
Pseudocode, a flowchart, and program code can all describe the same underlying procedure.
Practice
Procedure to Formula
Input \(x\), multiply by \(4\), then subtract \(2\). What formula does the algorithm compute?
Check Answer
\[ \boxed{4x-2}. \]Branching
Write the output rule for:
- If \(x>0\), return \(x\).
- Otherwise, return \(0\).
Check Answer
\[ \boxed{ f(x)= \begin{cases} x,&x>0,\\ 0,&x\leq0. \end{cases} } \]Termination
Does the procedure “start with positive integer \(n\) and repeatedly replace \(n\) with \(n-1\) while \(n>0\)” terminate?
Check Answer
Yes. Each step decreases \(n\) by \(1\), so after finitely many steps it reaches \(0\).
Efficiency
Can two algorithms produce the same correct output while requiring different amounts of work?
Check Answer
Yes. Correctness and efficiency are different properties.
Representation
Is a flowchart necessarily a different algorithm from pseudocode describing the same steps?
Check Answer
No. They may be two representations of the same underlying algorithm.
The Deeper Idea
Algorithms turn mathematical actions into explicit structure.
\[ \boxed{ \text{input} \longrightarrow \text{ordered operations and decisions} \longrightarrow \text{output} } \]This brings together several foundational ideas:
- functions connect inputs with outputs,
- logic controls branching,
- sequences describe repeated states,
- variables store changing values,
- representations let one process appear as words, formulas, flowcharts, or code.
Computational thinking begins when we stop asking only, “What is the answer?” and also ask:
- What sequence of steps reliably produces the answer?
- Why does the procedure work?
- Will it stop?
- Can it be made more efficient?
Those questions make algorithms useful far beyond programming.
Summary
- A procedure is an ordered method for carrying out a task.
- An algorithm is a finite, well-defined procedure for transforming input into output or accomplishing a specified task.
- Inputs, steps, outputs, and stopping conditions are basic algorithmic components.
- Step order matters.
- Algorithmic instructions should be precise and unambiguous.
- Deterministic algorithms produce the same result from the same input and state.
- Branching uses logical conditions to choose among paths.
- Iteration repeats operations while or until a condition is satisfied.
- Termination asks whether the algorithm eventually stops.
- Correctness asks whether the algorithm produces the intended result for valid inputs.
- Efficiency concerns the amount of work, time, memory, or other resources required.
- Natural language, pseudocode, flowcharts, formulas, and code can represent the same algorithm.
- Many mathematical procedures are algorithms even when no computer is involved.
An algorithm is mathematics made procedural. It describes not just a result, but a reproducible route from starting information to an outcome. That route can then be analyzed, checked, improved, and reused.
Algorithms and Computational Thinking
- Previous: Scientific Notation and Orders of Magnitude
- Algorithms and Computational Thinking — return to the lesson directory.