Explanation of Big O notation

01-big-o.md

For example, take this sorting algorithm:

void bubble_sort(int *array, size_t count) {
    for (size_t n = 0; n < count - 1; n++) {
        for (size_t i = 0; i < count - 1; i++) {
            size_t j = i + 1;
            if (array[j] < array[i]) {
                swap(&array[i], &array[j]);
            }
        }
    }
}

This algorithm will perform (count - 1)² = count² - 2*count + 1 comparisons. For Big O we usually remove the leading coefficient as well as the rest of the terms, which leaves us with O(n²)

The reason behind this removal is that, as n goes to infinity, the n² term will grow larger and the rest of the terms will be insignificant in comparison.

This is the code GLG wrote (with the formatting fixed and some aclaratory comments written):

public void UpdateGOL() {
    int bsX = core.GameState.BoardSizeX();
    int bsY = core.GameState.BoardSizeY();
    
    int[,] oldBoard = new int[bsX, bsY];
    /* -- snip -- (copying board from the current board to oldBoard) */
    
    // These 2 loops depend on the size of the board (which is our n)
    // Thus, O(n²)
    for (int i = 0; i < bsX; i++) {
        for (int j = 0; j < bsY; j++) {
            int neighborCount = 0;
            
            // But these loops always run the same amount of times (the compiler could easily unroll them)
            // Thus, this part is O(1)
            for (int x = -1; x <= 1; x++) {
                for (int y = -1; y <= 1; y++) {
                    // ensuring we don't count ourselves
                    if (x == 0 && y == 0) continue;
                    // ensuring we stay inside the board
                    if (i + x < 0 || i + x >= bsX || j + y < 0 || j + y >= bsY) continue;
                    
                    if (oldBoard[i, j] == 1) {
                        if (neighborCount <= 1 || neighborCount > 3) {
                            visualBoard[i, j].SetMaterial(true);
                        }
                    } else {
                        if (neighborCount == 3) visualBoard[i, j].SetMaterial(false);
                    }
                }
            }
            
        }
    }
    // In total, this algorithm runs in O(n²) time (or O(n*m) if you want to separate the width and height of the board)
}

02-bubble-sort.c

// Program I used to test the bubble sort implementation
// Why is Github so bad at highlighting C?
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void bubble_sort(int *array, size_t count) {
    for (size_t n = 0; n < count - 1; n++) {
        for (size_t i = 0; i < count - 1; i++) {
            size_t j = i + 1;
            if (array[j] < array[i]) {
                swap(&array[i], &array[j]);
            }
        }
    }
}

void print_array(const int *array, size_t count) {
    for (size_t i = 0; i < count; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main(int argc, char **argv) {
    argc--; argv++;

    size_t count = argc;
    int *array = malloc(sizeof(*array)*count);
    for (size_t i = 0; i < count; i++) {
        array[i] = atoi(argv[i]);
    }

    bubble_sort(array, count);
    print_array(array, count);
}