1. Algorithms
Definition – Algorithm
An algorithm is a method or process followed to solve a problem. It takes the input of a problem and transforms it into the output — a mapping from inputs to outputs. One problem can have many algorithms.
Properties of an algorithm
An algorithm must:
- be correct;
- be composed of a series of concrete steps;
- have no ambiguity about which step is performed next;
- be composed of a finite number of steps;
- terminate.
Definition – Program
A computer program is an instance (concrete representation) of an algorithm in some programming language.
2. Algorithm Efficiency and Analysis
Two (sometimes conflicting) design goals
| Goal | Concern of |
|---|---|
| (1) Algorithm easy to understand, code, debug | Software Engineering |
| (2) Algorithm that uses the computer’s resources efficiently | Data structures & algorithm analysis |
Definition – Algorithm analysis
Determining the resources a program implementing the algorithm will need. A working program is not enough — we also care about computation time and memory space. (Disk–CPU transfers, network traffic… also matter but depend on hardware.)
3. Measuring Efficiency
| Method | Pros / cons |
|---|---|
| Empirical comparison (run the programs) | Hard to do “fairly”, time consuming; depends on machine load, OS, compiler, problem size, specific input values |
| Mathematical / asymptotic analysis | Independent of machine; expresses running time as a function of input size |
Critical resources: time, space (disk, RAM), programmer effort, ease of use.
Definition –
For most algorithms, running time depends on the size of the input . It is written .
4. Faster Computer or Faster Algorithm?
If we buy a computer 10× faster, in the same time we can now solve size where .
| Change | ||||
|---|---|---|---|---|
| 1 000 | 10 000 | 10 | ||
| 500 | 5 000 | 10 | ||
| 250 | 1 842 | 7.37 | ||
| 70 | 223 | 3.16 | ||
| 13 | 16 | — |
Worked example – where the numbers come from
- : → .
- : → .
⚠️ Faster hardware barely helps exponential algorithms (only +3 in input size). A better algorithm beats a faster machine.
5. Complexity
Definition – Time complexity
The time taken by an algorithm to solve a problem.
Definition – Space complexity
The memory space used by an algorithm to solve a problem.
Definition – Complexity function
Analyzing complexity = finding , where is the size of the data and the cost (in time or space units).
| Problem | is… |
|---|---|
| Find an item in an array | number of elements in the array |
| Sort a list | size of the list |
| Towers of Hanoi | number of disks |
6. Mathematical Analysis
Worked example – exact cost of selection sort
for (int i = 0; i < n; i++) // c1 (increment + test)
{ int min = i; // c2 (assignment)
for (int j = i; j < n; j++) // c3
if (A[j] < A[min]) // c4 (comparison)
min = j; // c5 (assignment)
swap(A, i, min); // c6 (function call)
}Let and :
So is a quadratic polynomial in .
7. Asymptotic Analysis
Purpose: simplify analysis by dropping unnecessary detail, focusing on how cost grows as (usually in the worst case). Three classes: , , .
Definition – Big-O (asymptotic upper bound)
“The algorithm always executes in fewer than steps for large .”
Definition – Big-Omega (asymptotic lower bound)
Definition – Big-Theta (asymptotic equivalence)
Properties
Worked example – proving a bound
Show .
- Upper: . Take → .
- Lower: for all . Take → .
- Both hold → .
⚠️ is only an upper bound: is true but not tight. Use when you mean “exactly this growth rate”.
8. Simplifying Rules
Rule 1 – Transitivity
If and then .
Rule 2 – Constants
If for a constant , then .
Rule 3 – Sum
If and then .
Rule 4 – Product
If and then .
In practice: ignore constants, drop low-order terms. The same rules hold for (and so for ).
9. Calculation Rules
| Rule | Statement |
|---|---|
| R1 | An elementary operation costs |
| R2 | A sequence of instructions costs the sum of the costs |
| R3 | if / switch: the maximum of the branches |
| R4 | Loop: cost of the body × number of iterations |
| R5 | Function: cost of its body; the call itself is |
Worked example – selection sort with the rules
for (int i = 0; i < n; i++) // O(n) iterations
{ int min = i; // O(1)
for (int j = i; j < n; j++) // O(n) iterations
if (A[j] < A[min]) // O(1)
min = j;
swap(A, i, min); // O(1)
}
10. Exercises (slides 16–17)
| Code | Complexity | Why |
|---|---|---|
for(i=1;i<=n;i++) sum+=n; | iterations of | |
for i=1..n / for j=1..n-1 / sum++ | iterations | |
for j=1..n / for i=1..j / sum++, then for k=0..n-1: A[k]=k | , plus → sum rule | |
Two nested loops 1..n × 1..n then 1..n × 1..i | ||
for(k=1;k<=n;k*=2) / for j=1..n | outer runs times, inner |
⚠️ A loop whose counter doubles (
k*=2) or halves runs times, not .
11. Complexity of Recursive Algorithms
Methods for solving recurrences
- Guess and verify: guess , then prove (or ) by induction.
- Expansion: successive substitutions from down to , which is known.
Worked example – recursive factorial
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}Recurrence: .
By expansion:
By guessing: levels of recursion × work (test + return) per level .
flowchart LR F4["fact(4)"] --> F3["fact(3)"] --> F2["fact(2)"] --> F1["fact(1) = 1"]
4 calls for → calls in general.
12. Space Complexity
- Usually counted in number of elements (an element = one data item).
- Recursion can cost much more space than iteration because each pending call occupies stack space.
| Factorial version | Space |
|---|---|
| Iterative | |
| Recursive | ( stacked calls) |
13. Classes of Complexity Functions
Ordered from slowest-growing (best) to fastest-growing (worst):
| Class | Name |
|---|---|
| constant | |
| logarithmic | |
| linear | |
| linearithmic / loglinear / quasilinear | |
| quadratic | |
| cubic | |
| polynomial | |
| or | exponential |
| factorial |
14. Growth of Complexity Functions – Example
Time needed assuming 1 µs per elementary operation:
| Notation | ||||||
|---|---|---|---|---|---|---|
| 1 µs | 1 µs | 1 µs | 1 µs | 1 µs | 1 µs | |
| 3 µs | 7 µs | 10 µs | 13 µs | 17 µs | 20 µs | |
| 10 µs | 100 µs | 1 ms | 10 ms | 100 ms | 1 s | |
| 33 µs | 664 µs | 10 ms | 13.3 ms* | 1.6 s | 20 s | |
| 100 µs | 10 ms | 1 s | 1.7 min | 16.7 min* | 11.6 days | |
| 1 ms | 1 s | 16.7 min | 11.6 days | 31.7 years | 31 709 years | |
| 10 ms* | years |
⚠️ *Entries copied from the slide that don’t match a recomputation: at is ms; at is µs hours; µs ms. The point of the table (exponential and high polynomial costs explode) is unchanged.