Introduction to Algorithms

An algorithm is a finite sequence of unambiguous steps that transforms an input into a desired output. Before comparing algorithms, we need to agree on what qualifies as one — and on what “better” means.

Properties every algorithm must have

• Input — zero or more externally supplied values.
• Output — at least one result is produced.
• Definiteness — every step is clear and unambiguous.
• Finiteness — it terminates after a finite number of steps (a program that can loop forever is not an algorithm in the formal sense).
• Effectiveness — each step is basic enough to be carried out exactly, in principle even by hand.

Algorithm vs. program

A program is an implementation of an algorithm in a specific language. Exams love this distinction: an algorithm is analysed before implementation (design time, usually in pseudocode), a program is what actually runs. An operating system, being intentionally non-terminating, is the classic example of a program that is not an algorithm.

How do we compare algorithms?

Running two implementations and timing them is unreliable — results change with the machine, the compiler, the input, even the room temperature of the benchmark. Instead we do a-priori analysis: count how the number of basic operations grows as a function of the input size n, independent of any machine. That growth function is what the next lessons formalise as time complexity.

Key takeaways

• Definiteness and finiteness are the two properties exam questions test most.
• Analysis is machine-independent by design — we count operations, not seconds.
• The input size n is the single variable everything is measured against.