What Is an Algorithm | Algorithms I

Definition

An algorithm is a finite sequence of well-defined steps that takes some value(s) as input and produces some value(s) as output. Three properties characterise every algorithm: it must terminate (halt) on all valid inputs, each step must be unambiguously specified, and it must produce the correct output for every input instance.

The problem an algorithm solves is separate from the algorithm itself. A problem specifies the input/output relationship (e.g. “reorder a sequence into non-decreasing order”), whilst an instance is a concrete input (e.g. [9, 102, 10, -7, 64, 18]). Many different algorithms can solve the same problem.

Examples

Insertion Sort

Build a sorted prefix by taking each next element and inserting it into the correct position, shifting larger elements right to make room. The algorithm terminates because the outer loop runs a fixed number of iterations and the inner loop always decrements towards zero.

Euclid’s GCD

Repeatedly replace the larger number by the remainder when dividing by the smaller: $\gcd(a, b) = \gcd(b, a \bmod b)$ . Terminates because the remainders form a strictly decreasing sequence of non-negative integers.

The RAM Model

To analyse algorithms independently of hardware, we assume an idealised machine (the Random Access Machine model):

Creating an array of size $m$ takes time proportional to $m$ .
Accessing any array element $A[i]$ takes constant time.
All numerical operations (addition, comparison, multiplication) take constant time.
Each array cell holds one data item.

This model abstracts away CPU caches, pipelining, and the fact that storing a pointer to an $n$ -element array requires $\Theta(\log n)$ bits. The RAM model is the conventional mathematical playground for algorithm analysis; it is often a good approximation to real performance unless large constants, cache effects, or small problem sizes dominate.

Problem vs Algorithm

Problem	Algorithm
Sorting	Insertion Sort, MergeSort, QuickSort, HeapSort
Shortest path	Dijkstra’s, Bellman-Ford
Primality testing	Trial division, Miller-Rabin

A problem defines what to compute; an algorithm defines how to compute it. The efficiency of different algorithms for the same problem can differ dramatically (compare Insertion Sort’s $\Theta(n^2)$ with MergeSort’s $\Theta(n \log n)$ ).

Summary

Concept	Description
Algorithm	Finite sequence of well-defined steps, takes input, produces output, terminates
Problem	Specification of input/output relationship
Instance	Concrete input of a specific size
Correctness	Algorithm halts with correct output for every input instance
RAM model	Unit-cost operations for arithmetic, comparisons, memory access
Why abstract	Enables asymptotic analysis independent of hardware details