Tutorial 2: Analysis of Algorithms

CAB301 - Algorithms and Complexity

School of Computer Science, Faculty of Science

Agenda

  1. Recap:
    1. Theoretical Analysis of Algorithms
    2. Big- Notation
    3. Empirical Analysis
  2. Tutorial Questions
    1. Part A: Big- Notation - mostly following definitions
    2. Part B: Theoretical Analysis - efficiency class with summation
    3. Part C: Empirical Analysis - efficiency class with experiments
CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Steps to Analyse an Algorithm, Theoretically

For example, let's consider an algorithm that sorts a list of numbers.

  1. Decide the parameter(s) characterising the input size. E.g., the number of elements in the list, .
  2. Identify the algorithm's basic operation(s). E.g., a swap, or a comparison of two numbers.
  3. Identify the case scenario(s) that will determine the algorithm's running time. E.g., best, worst, or average (sorted, reversed-sorted, or random list).
  4. Set up a summation formula for the number of times the basic operation is performed in the worst-case scenario.
  5. Solve the summation formula using standard arithmetic rules and define the efficiency class in big- notation.
CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Big- Notation

The upper bound of an algorithm's running time, i.e., the worst-case scenario.

Consider the following nested for-loop in pseudocode:

for to do
for to do

Here, if is the time taken to execute the basic operation , then:

And the efficiency class is .
CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Empirical Analysis

Set up either a counter, or a timer to measure the algorithm's running time.

int x = 0;
int counter = 0;
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        x = x + 1;
        counter++; // Increment the counter after each basic operation
    }
}

Then try different values of and find how the running time grows.

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science