C++UCS301
Algorithm AnalysisC++17

Algorithms & Analysis

An algorithm is a finite, unambiguous sequence of steps that transforms input into output. Analysis predicts resource use independently of a particular machine.

What to understand

  • Correctness and termination
  • Input size as the independent variable
  • Operation counting
  • Best, average, and worst cases

Remember this

  1. 1Analyse growth, not stopwatch time
  2. 2State the input size clearly
  3. 3Correctness comes before efficiency

Detailed notes

An algorithm is more than code: it is a language-independent method whose inputs, outputs, steps, and stopping condition are precisely defined. Two programs can implement the same algorithm while differing in syntax, constants, and hardware behaviour.

Analysis builds a cost model around a chosen basic operation—such as a comparison, assignment, or edge relaxation—and expresses how often it runs as input size n grows. This lets us compare solutions before choosing a compiler or machine.

How it works

  1. 1Define the input size and required output.
  2. 2State the invariant that remains true during execution.
  3. 3Count the dominant operation for representative cases.
  4. 4Prove termination and argue that the final state satisfies the specification.

Where it is used

  • Comparing two solutions during design
  • Predicting whether a program will handle production-scale input
  • Explaining correctness in exams and code reviews

Common mistakes

  • Benchmarking tiny inputs and calling that analysis
  • Counting source lines instead of executed operations
  • Optimising an incorrect or non-terminating procedure

C++ implementation

C++17 reference
main.cpp

Count the dominant operation

The comparison runs n times, so the running time grows linearly.

#include <iostream>
#include <vector>
using namespace std;

int maximum(const vector<int>& values) {
    int answer = values.front();
    for (int value : values) {          // n iterations
        if (value > answer) answer = value;
    }
    return answer;
}

int main() {
    vector<int> values{7, 2, 19, 4, 11};
    cout << maximum(values) << '\n';
}
16 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.