📐

Algorithms Beginner

What algorithms are, how to measure their cost with Big-O notation, and the essential building-blocks: linear search, binary search, and the O(n²) sorting algorithms.

8 lessons 19 tasks

Lessons Quiz Certificate

📚 Lessons

1 What Is an Algorithm?

An algorithm is a finite, unambiguous sequence of steps that solves a well-defined problem. Three properties are required: finiteness (it must terminate), definiteness (each step is precise), and effectiveness (each step is executable). The same problem may have many algorithms with very different costs.

Input: zero or more values
Output: one or more values related to the input
Correctness: for every valid input the output satisfies the specification

Algorithm MAX(A, n):
  max ← A[0]
  for i ← 1 to n-1:
    if A[i] > max: max ← A[i]
  return max

// Find the maximum element in an array
function arrayMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}
console.log(arrayMax([3, 1, 4, 1, 5, 9, 2, 6])); // 9

2 Big-O Notation and Complexity

Big-O notation describes the asymptotic upper bound on an algorithm's running time (or space) as the input size n grows. Formally, f(n) = O(g(n)) means there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

Common classes in ascending order of growth:

O(1) — constant: array index lookup
O(log n) — logarithmic: binary search
O(n) — linear: single pass over an array
O(n log n) — linearithmic: merge sort
O(n²) — quadratic: bubble sort
O(2ⁿ) — exponential: naive subset enumeration

We ignore constant factors and low-order terms: 3n² + 5n + 7 = O(n²).

// Counting operations to build intuition
function countOps(n) {
  let ops = 0;
  // O(1) block
  ops++;                          // 1 op
  // O(n) block
  for (let i = 0; i < n; i++) ops++;      // n ops
  // O(n^2) block
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) ops++;    // n^2 ops
  return ops; // ≈ n^2 dominates
}

3 Linear Search — O(n)

Linear search scans each element left to right until it finds the target or exhausts the array. No ordering assumption is needed.

Correctness invariant: after examining indices 0 … i−1, none of them equals the target. If the loop completes without returning, the target is absent.

Complexity:

Best case: Ω(1) — target at index 0
Worst case: O(n) — target absent or at last position
Average case: Θ(n/2) = Θ(n) — expected position is the middle

// Linear search — returns index or -1
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}
console.log(linearSearch([4, 2, 7, 1, 9], 7)); // 2
console.log(linearSearch([4, 2, 7, 1, 9], 5)); // -1

4 Binary Search — O(log n)

Binary search finds a target in a sorted array by repeatedly halving the search interval.

Loop invariant: if the target exists in the array, it lies within A[lo … hi].

Recurrence for comparisons: T(n) = T(n/2) + Θ(1), which solves to T(n) = Θ(log n) by the master theorem (case 2 with a=1, b=2, f(n)=Θ(1)).

BINARY-SEARCH(A, lo, hi, target):
  while lo ≤ hi:
    mid ← ⌊(lo + hi) / 2⌋
    if A[mid] = target: return mid
    if A[mid] < target: lo ← mid + 1
    else:               hi ← mid − 1
  return −1

// Binary search — array must be sorted
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid - 1;
  }
  return -1;
}
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4)); // -1

5 Bubble Sort — O(n²)

Bubble sort repeatedly compares adjacent pairs and swaps them if out of order. After k passes, the k largest elements are in their correct positions at the right end.

Loop invariant: after pass k, elements A[n−k … n−1] are the k largest values and are in sorted order.

Comparisons: (n−1) + (n−2) + … + 1 = n(n−1)/2 = Θ(n²). An early-exit optimisation gives O(n) on already-sorted input.

// Bubble sort with early-exit optimisation
function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let pass = 0; pass < n - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < n - 1 - pass; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return a;
}
console.log(bubbleSort([5, 3, 8, 1, 2])); // [1,2,3,5,8]

6 Selection Sort — O(n²)

Selection sort finds the minimum of A[i … n−1] and swaps it into position i, then increments i.

Loop invariant: at the start of iteration i, A[0 … i−1] contains the i smallest elements in sorted order.

Comparisons: exactly n(n−1)/2 = Θ(n²) regardless of input order. Swaps: at most n−1, which can be advantageous when writes are expensive.

// Selection sort — O(n^2) comparisons, O(n) swaps
function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}
console.log(selectionSort([64, 25, 12, 22, 11])); // [11,12,22,25,64]

7 Insertion Sort — O(n²)

Insertion sort builds a sorted sub-array A[0 … i] by taking element A[i+1] and sliding it left until it is in position.

Loop invariant: at the start of iteration i, the sub-array A[0 … i−1] is sorted.

Complexity: worst case Θ(n²) (reverse-sorted input); best case Θ(n) (already sorted, only one comparison per element). Excellent for small or nearly-sorted arrays.

Arithmetic series fact: Σᵢ₌₁ⁿ i = n(n+1)/2 — the total shifts in the worst case.

// Insertion sort
function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // [1,2,3,4,5,6]

8 Arithmetic Series and Counting Operations

Many algorithm analyses reduce to summing arithmetic series. The key formula is:

Σᵢ₌₁ⁿ i  =  1 + 2 + 3 + … + n  =  n(n+1)/2  =  Θ(n²)

This arises when an inner loop runs i times for each value of i in an outer loop (e.g., bubble sort and insertion sort worst-case). Similarly:

Σᵢ₌₀ⁿ 2ⁱ = 2ⁿ⁺¹ − 1 = Θ(2ⁿ) — geometric series (binary tree levels)
Σᵢ₌₁ⁿ 1/i ≈ ln n = Θ(log n) — harmonic series (arises in some average-case analyses)

// Verify arithmetic series: count ops in nested loop
function countNestedOps(n) {
  let ops = 0;
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= i; j++)
      ops++;
  return ops; // equals n*(n+1)/2
}
for (const n of [5, 10, 20]) {
  const formula = n * (n + 1) / 2;
  console.log(n, countNestedOps(n), formula); // always equal
}

📝 Tasks

19 tasks across 7 pages — multiple-choice and fill-in (type the answer). Score 70% or higher to earn your certificate.

🎓 Certificate of Completion

🔒 Pass the quiz above (70%+) to unlock your downloadable certificate.