📐

Algorithms Intermediate

Divide-and-conquer, merge sort, quicksort, the master theorem, recursion, hashing, stacks, queues, and two-pointer techniques.

8 lessons 19 tasks

Lessons Quiz Certificate

📚 Lessons

1 Divide and Conquer

Divide and conquer splits a problem of size n into a subproblems of size n/b, solves them recursively, and combines results in f(n) time. This yields the recurrence:

T(n) = a · T(n/b) + f(n)

The technique works well when subproblems are independent (no overlapping sub-sub-problems) and combining is cheap. Classic examples: merge sort, quicksort, binary search, Karatsuba multiplication.

a = number of recursive calls
b = factor by which input shrinks per call
f(n) = cost of divide + combine steps

// Generic divide-and-conquer skeleton
function divideAndConquer(arr, lo, hi) {
  if (hi - lo <= 0) return solve(arr[lo]); // base case
  const mid = Math.floor((lo + hi) / 2);
  const left  = divideAndConquer(arr, lo, mid);
  const right = divideAndConquer(arr, mid + 1, hi);
  return combine(left, right); // O(n) combine step
}

2 Merge Sort — Θ(n log n)

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves in Θ(n) time.

Recurrence: T(n) = 2T(n/2) + Θ(n). Applying the master theorem with a=2, b=2, f(n)=Θ(n): log_b(a) = log₂2 = 1, and f(n) = Θ(n¹), so case 2 applies, giving T(n) = Θ(n log n).

Invariant during merge: the output array contains the smallest elements seen so far in sorted order.

Merge sort is stable and its worst case equals its best case: always Θ(n log n). Space: Θ(n) auxiliary.

// Merge sort — Θ(n log n) stable sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(L, R) {
  const result = [];
  let i = 0, j = 0;
  while (i < L.length && j < R.length)
    result.push(L[i] <= R[j] ? L[i++] : R[j++]);
  return result.concat(L.slice(i)).concat(R.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82])); // sorted

3 Quicksort — Θ(n log n) average

Quicksort picks a pivot, partitions elements into those ≤ pivot and those > pivot, then sorts each partition recursively.

Average-case recurrence (random pivot): T(n) = 2T(n/2) + Θ(n) → Θ(n log n).

Worst case (always picking min or max as pivot on sorted input): T(n) = T(n−1) + Θ(n) → Θ(n²).

Random pivot selection makes worst case extremely unlikely. Quicksort is often faster in practice than merge sort due to better cache behaviour and in-place partitioning (space O(log n) for the call stack).

// Quicksort with random pivot
function quicksort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  // random pivot to avoid worst case
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];
  const p = partition(arr, lo, hi);
  quicksort(arr, lo, p - 1);
  quicksort(arr, p + 1, hi);
}
function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++)
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

4 The Master Theorem

The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:

Case 1: if f(n) = O(n^(log_b(a)−ε)) for some ε > 0, then T(n) = Θ(n^log_b(a))
Case 2: if f(n) = Θ(n^log_b(a)), then T(n) = Θ(n^log_b(a) · log n)
Case 3: if f(n) = Ω(n^(log_b(a)+ε)) and a·f(n/b) ≤ c·f(n) for some c < 1, then T(n) = Θ(f(n))

Example — merge sort: a=2, b=2, f(n)=n
  log_b(a) = log₂2 = 1 → compare n¹ with f(n)=n → Case 2
  T(n) = Θ(n log n)

Example — binary search: a=1, b=2, f(n)=1
  log₂1 = 0 → compare n⁰=1 with f(n)=1 → Case 2
  T(n) = Θ(log n)

// Demonstrating recurrence depth with call counting
function mergeSortCount(arr, depth = 0) {
  if (arr.length <= 1) return { arr, calls: 1 };
  const mid = Math.floor(arr.length / 2);
  const L = mergeSortCount(arr.slice(0, mid), depth + 1);
  const R = mergeSortCount(arr.slice(mid),    depth + 1);
  return {
    arr: merge(L.arr, R.arr),
    calls: 1 + L.calls + R.calls,
  };
}
// For n=8: 15 calls total = 2^(log2(8)+1) - 1 (full binary tree)

5 Stacks and Queues

Stack (LIFO): push and pop from the same end. Push and pop are O(1). Used in function call frames, expression parsing, DFS.

Queue (FIFO): enqueue at the rear, dequeue from the front. Both operations O(1) with a circular buffer or linked list. Used in BFS, task scheduling.

These are abstract data types — the same Big-O guarantees hold regardless of implementation (array or linked list).

// Stack and Queue using JavaScript arrays
class Stack {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); }          // O(1) amortised
  pop()   { return this.data.pop(); }     // O(1)
  peek()  { return this.data[this.data.length - 1]; }
  get size() { return this.data.length; }
}
class Queue {
  constructor() { this.data = []; }
  enqueue(v) { this.data.push(v); }       // O(1) amortised
  dequeue()  { return this.data.shift(); }// O(n) — use linked list for O(1)
  get size() { return this.data.length; }
}

6 Hash Tables — O(1) Average

A hash table stores key-value pairs using a hash function h(k) that maps key k to a bucket index. Average-case time for insert, delete, and lookup is O(1).

Load factor: α = n/m, where n is the number of keys and m is the number of buckets. When α is kept below a constant (e.g., 0.75) by resizing, expected chain length is O(1).

Collision resolution:

Chaining: each bucket holds a linked list; lookup is O(1 + α)
Open addressing: probe for the next empty slot; works well for α < 0.7

Worst case (all keys collide): O(n). A good hash function makes this astronomically unlikely.

// JavaScript Map is a hash table
const freq = new Map();
const words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'];
for (const w of words) {
  freq.set(w, (freq.get(w) ?? 0) + 1); // O(1) average each
}
console.log([...freq.entries()]);
// [['apple',3],['banana',2],['cherry',1]]

7 Two-Pointer Technique

The two-pointer technique uses two indices that move through an array to find pairs or sub-arrays satisfying a condition, reducing an O(n²) brute force to O(n).

Correctness argument: on a sorted array, if A[lo] + A[hi] > target then hi must decrease (A[hi] is too large); if the sum < target then lo must increase. All pairs are covered without revisiting.

// Two-sum on a sorted array — O(n)
function twoSumSorted(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const sum = arr[lo] + arr[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;
    else              hi--;
  }
  return null;
}
console.log(twoSumSorted([1, 2, 3, 4, 6], 6)); // [1, 3] → 2+4

8 Sliding Window

The sliding window technique maintains a contiguous sub-array (the window) and slides it across the input, updating an aggregate in O(1) per step. Total time: O(n).

Key insight: instead of recomputing the aggregate from scratch (O(k) per window, O(nk) total), add the new element and subtract the leaving element.

// Maximum sum of any sub-array of length k — O(n)
function maxSumWindow(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // slide: add new, remove old
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}
console.log(maxSumWindow([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

📝 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.