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:

  1. be correct;
  2. be composed of a series of concrete steps;
  3. have no ambiguity about which step is performed next;
  4. be composed of a finite number of steps;
  5. 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

GoalConcern of
(1) Algorithm easy to understand, code, debugSoftware Engineering
(2) Algorithm that uses the computer’s resources efficientlyData 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

MethodPros / 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 analysisIndependent 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 00010 00010
5005 00010
2501 8427.37
702233.16
1316—

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 arraynumber of elements in the array
Sort a listsize of the list
Towers of Hanoinumber 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)

n c·g(n) f(n) n₀ f(n) ≤ c·g(n) for all n ≥ n₀ → f ∈ O(g)

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

RuleStatement
R1An elementary operation costs
R2A sequence of instructions costs the sum of the costs
R3if / switch: the maximum of the branches
R4Loop: cost of the body × number of iterations
R5Function: 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)

CodeComplexityWhy
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..nouter runs times, inner

⚠️ A loop whose counter doubles (k*=2) or halves runs times, not .


11. Complexity of Recursive Algorithms

Methods for solving recurrences

  1. Guess and verify: guess , then prove (or ) by induction.
  2. 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 versionSpace
Iterative
Recursive ( stacked calls)

13. Classes of Complexity Functions

Ordered from slowest-growing (best) to fastest-growing (worst):

ClassName
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 µs1 µs1 µs1 µs1 µs1 µs
3 µs7 µs10 µs13 µs17 µs20 µs
10 µs100 µs1 ms10 ms100 ms1 s
33 µs664 µs10 ms13.3 ms*1.6 s20 s
100 µs10 ms1 s1.7 min16.7 min*11.6 days
1 ms1 s16.7 min11.6 days31.7 years31 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.