Analysing algorithms

Introduction

An algorithm is a precise list of steps that solves a problem: sort these marks, find the shortest route, choose the cheapest set of coins. Usually several algorithms solve the same problem, and they can differ enormously in speed. This course teaches the standard ones, and how to tell which is faster before running them.

It uses C, and assumes the Data Structures course (arrays, linked lists, stacks, queues, trees, heaps, graphs).

Speed is not something you have to discover by running a program. Reading its loops tells you how the work will grow, long before you have a million items to test with.

How it works

How fast they grow

#include <stdio.h>
#include <math.h>

int main(void) {
    double sizes[] = {10, 1000, 1000000};
    printf("%9s %8s %14s %16s\n", "n", "log2 n", "n log2 n", "n^2");
    for (int i = 0; i < 3; i++) {
        double n = sizes[i];
        printf("%9.0f %8.1f %14.0f %16.0f\n", n, log2(n), n * log2(n), n * n);
    }
    return 0;
}

For a million items, an O(n²) algorithm does a trillion steps (minutes or hours), while O(n log n) does about 20 million (a fraction of a second). That difference is why sorting algorithms matter.

Best, worst and average case

The same algorithm can take different numbers of steps on different inputs of the same size. Linear search finds the first item in 1 comparison (the best case), and a missing item after n comparisons (the worst case). When we just say "linear search is O(n)", we mean the worst case, because it is a promise that holds for every input.

Syntax

There is no new C in this lesson, only a way of describing loops:

for (i = 0; i < n; i++)            O(n)        once per item
two nested loops over n            O(n²)       once per pair
for (m = n; m > 1; m /= 2)         O(log n)    once per halving
an O(log n) loop inside O(n)       O(n log n)

Example

#include <stdio.h>

int main(void) {
    int n = 8;
    int pairs = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            pairs++;   // runs n*(n-1)/2 times: O(n^2)
    int halvings = 0;
    for (int m = n; m > 1; m /= 2)
        halvings++;    // runs log2(n) times: O(log n)
    printf("n = %d: %d pairs, %d halvings\n", n, pairs, halvings);
    return 0;
}

Watch the two counters. The nested loops look at every pair i < j once: that is n(n-1)/2 pairs, 28 for n = 8. The second loop halves m each time, so it runs only about log₂ n times, 3 for n = 8.

Most loops fall into a few shapes:

Big-O keeps only the fastest-growing term and drops constants: n(n-1)/2 = n²/2 - n/2 is O(n²).

Line by line

1. n is the size of the input, and pairs will count how often the inner statement runs.
2. The outer loop chooses i. The inner loop starts at i + 1, so each pair of positions is met exactly once.
3. For n = 8, pairs++ runs 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 times.
4. The second loop starts m at 8 and halves it: 8, 4, 2, and then 1 stops the loop. halvings++ ran 3 times.
5. printf shows both counts, so you can compare them with the formulas n(n-1)/2 and log₂ n.

Expected result

n = 8: 28 pairs, 3 halvings

In the real world

Before a team commits to a design, someone usually asks how it behaves with a hundred times the data. A rough count like this one answers that in a minute, and it is also the most common question in technical interviews.

Common mistakes

• Counting the lines of code instead of how often each line runs.
• Calling two loops one after the other O(n²): side by side they add up to O(n), and only nesting multiplies.
• Saying an algorithm is fast because it was quick on ten items: Big-O is about what happens as n grows.

Best practices

• Find the innermost statement first and ask how often it runs.
• Add a counter to the code to check your formula on a small input.
• Say which case you mean: best, worst or average.

Summary

An algorithm's cost is the number of steps it performs as a function of the input size. Big-O keeps the fastest-growing term, loop shapes give the common classes, and the worst case is the usual promise.

Mark lesson complete