<aside> ⚡ Big-O notation describes the upper bound of an algorithm's runtime as the input size grows

</aside>

• Disregards lower time complexity terms
• Time complexities for various operations and algorithms:
  • Simple operations are constant time: O(1).
  • Looping from 0 to n (or similar patterns) typically has linear time complexity: O(n).
  • Nested loops over the same range lead to quadratic time complexity: O(n²).
  • Recursion can lead to various complexities, such as O(n) for factorial calculation or O(log n) for binary search.
  • Matrix multiplication is cubic time complexity: O(n³).
  • Exponential algorithms like the traveling salesperson problem are O(2ⁿ), which are impractical for large n.

Linear Search

int linear_search(int a[], int n, int X) {
    for (int i = 0; i < n; i++) {
        if (a[i] == X) return i;
    }
    return -1;
}

Matrix Multiplication

void matrix_multiply(double a[N][N], double b[N][N], double c[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

Insertion Sort

• Best case time complexity of $O(n)$ and average/worst-case of $O(n^2)$

void insertion_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j > 0 && a[j] < a[j-1]; j--) {
            int temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
}

Factorial Calculation

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Recursive Binary Search

bool binary_search(int a[], int first, int last, int key) {
    if (first > last) return false;
    int mid = (first + last) / 2;
    if (a[mid] == key) return true;
    else if (key < a[mid]) return binary_search(a, first, mid-1, key);
    else return binary_search(a, mid+1, last, key);
}

Quicksort

• Average and best-case time complexity of $O(n \log n)$ and worst case of $O(n^2)$

void quicksort(int a[], int begin, int end) {
    if (begin < end) {
        int pivotIndex = sortAndShuffle(a, begin, end);
        quicksort(a, begin, pivotIndex - 1);
        quicksort(a, pivotIndex + 1, end);
    }
}

int sortAndShuffle(int a[], int begin, int end) {
    int pivotValue = a[begin];
    int current = begin;
    for (int i = begin + 1; i <= end; i++) {
        if (a[i] <= pivotValue) {
            current++;
            int temp = a[current];
            a[current] = a[i];
            a[i] = temp;
        }
    }
    int temp = a[begin];
    a[begin] = a[current];
    a[current] = temp;
    return current;
}