Algorithms Midterm

Big-O (O)

Upper bound: "the algorithm takes AT MOST this long" (worst-case ceiling). Formal: f(n) = O(g(n)) if there are constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0. Example: 3n + 5 = O(n) because 3n + 5 ≤ 4n once n ≥ 5.

Big Omega (Ω)

Lower bound: "the algorithm takes AT LEAST this long." Formal: f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for all n ≥ n0. Example: 3n + 5 = Ω(n) because 3n + 5 ≥ 3n.

Big Theta (Θ)

Tight bound: the algorithm grows at EXACTLY this rate (both O and Ω). Formal: f(n) = Θ(g(n)) if c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0. Example: 3n + 5 = Θ(n).

How to calculate Big-O

1) Count the basic steps as a function of n. 2) Drop constants (5n → n). 3) Drop lower-order terms (n² + n → n²). 4) Keep the fastest-growing term. Example: 4n² + 10n + 7 → O(n²).

Growth order (slow to fast)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

Recurrence

An equation that defines a function in terms of itself on smaller inputs. In algorithms it describes the runtime of a recursive algorithm. Example (Mergesort): T(n) = 2T(n/2) + n means "solve two halves of size n/2, then do n work to combine." Base case: T(1) = constant.

Substitution Method

A way to solve a recurrence: 1) GUESS the answer (like T(n) = O(n log n)). 2) ASSUME it is true for smaller sizes (induction hypothesis). 3) PROVE it holds for n, picking a constant c that works. Example: T(n) = 2T(n/2) + n. Guess T(n) ≤ c·n·log n. Substitute: T(n) ≤ 2·c(n/2)log(n/2) + n = c·n·log n − c·n + n ≤ c·n·log n when c ≥ 1. So T(n) = O(n log n).

Master Theorem

A shortcut for recurrences of the form T(n) = a·T(n/b) + f(n), where a ≥ 1 (number of subproblems), b > 1 (shrink factor), f(n) = work outside the recursion. Compare f(n) to n^(log_b a). Case 1: f(n) smaller → T(n) = Θ(n^(log_b a)). Case 2: f(n) equal → T(n) = Θ(n^(log_b a) · log n). Case 3: f(n) bigger (and regular) → T(n) = Θ(f(n)).

Master Theorem example

Mergesort: T(n) = 2T(n/2) + n. a = 2, b = 2, so n^(log_2 2) = n. f(n) = n equals n → Case 2 → T(n) = Θ(n log n). Another: T(n) = 4T(n/2) + n. n^(log_2 4) = n². f(n) = n is smaller → Case 1 → Θ(n²). Another: T(n) = T(n/2) + n. n^(log_2 1) = 1. f(n) = n is bigger → Case 3 → Θ(n).

Recursive Algorithm

An algorithm that solves a problem by calling itself on smaller versions of the same problem until it reaches a base case. Needs: 1) a base case (stops recursion), 2) a recursive case (smaller input). Runtime is found with a recurrence. Pseudocode: Factorial(n): if n ≤ 1 return 1; return n * Factorial(n−1). Recurrence: T(n) = T(n−1) + O(1) → O(n). Best/Avg/Worst: depends on the algorithm; solve its recurrence.

Mergesort: runtime

Best: O(n log n). Average: O(n log n). Worst: O(n log n). Extra space: O(n). Stable. Idea: split in half, sort each half, merge. Recurrence: T(n) = 2T(n/2) + n.

Mergesort: pseudocode

MergeSort(A, left, right):  if left < right:   mid = (left + right) / 2   MergeSort(A, left, mid)   MergeSort(A, mid+1, right)   Merge(A, left, mid, right) Merge: copy both halves; repeatedly take the smaller front item of the two halves into A until both are empty.

Quicksort: runtime

Best: O(n log n) (pivot splits evenly). Average: O(n log n). Worst: O(n²) (pivot is always smallest/largest, e.g., sorted input with bad pivot). Extra space: O(log n). Not stable. Recurrence: T(n) = T(k) + T(n−k−1) + n.

Quicksort: pseudocode

QuickSort(A, low, high):  if low < high:   p = Partition(A, low, high)   QuickSort(A, low, p−1)   QuickSort(A, p+1, high) Partition(A, low, high):  pivot = A[high]; i = low − 1  for j = low to high−1:   if A[j] ≤ pivot: i = i+1; swap A[i], A[j]  swap A[i+1], A[high]  return i+1

Insertion Sort: runtime

Best: O(n) (already sorted). Average: O(n²). Worst: O(n²) (reverse sorted). Extra space: O(1). Stable. Idea: like sorting a hand of cards; insert each new item into its place in the sorted part.

Insertion Sort: pseudocode

InsertionSort(A):  for i = 1 to n−1:   key = A[i]   j = i − 1   while j ≥ 0 and A[j] > key:    A[j+1] = A[j]    j = j − 1   A[j+1] = key

Counting Sort: runtime

Best: O(n + k). Average: O(n + k). Worst: O(n + k). (k = range of values, n = number of items.) Extra space: O(n + k). Stable. Not comparison-based. Works for integers in a small range. Idea: count how many times each value appears, then place items.

Counting Sort: pseudocode

CountingSort(A, k):  C = array of size k+1, all 0  for each x in A: C[x] = C[x] + 1  for i = 1 to k: C[i] = C[i] + C[i−1]  for j = n−1 down to 0:   B[C[A[j]] − 1] = A[j]   C[A[j]] = C[A[j]] − 1  return B

Radix Sort: runtime

Best: O(d(n + k)). Average: O(d(n + k)). Worst: O(d(n + k)). (d = number of digits, k = base, e.g., 10.) Extra space: O(n + k). Stable. Idea: sort by the least significant digit first, then the next digit, and so on, using a stable sort (like Counting Sort) for each digit.

Radix Sort: pseudocode

RadixSort(A, d):  for digit = 1 to d (starting at the ones place):   use a stable sort (Counting Sort) to sort A by that digit Example: 170, 45, 75, 90 → sort by ones → sort by tens → sort by hundreds → 45, 75, 90, 170.

Bucket Sort: runtime

Best: O(n + k). Average: O(n + k) (data spread evenly). Worst: O(n²) (everything lands in one bucket). Extra space: O(n + k). Idea: spread items into buckets by value range, sort each bucket, then join them.

Bucket Sort: pseudocode

BucketSort(A):  create n empty buckets  for each x in A:   put x into bucket[floor(n * x)] (for values in [0,1))  for each bucket: sort it (usually Insertion Sort)  concatenate all buckets in order

Binary Sort (Binary Insertion Sort): runtime

Best: O(n log n) comparisons (O(n) data moves if already sorted). Average: O(n²). Worst: O(n²) because shifting items still costs O(n) each. Uses binary search to find where each item goes. Extra space: O(1). Stable.

Binary Sort: pseudocode

BinaryInsertionSort(A):  for i = 1 to n−1:   key = A[i]   pos = BinarySearch(A, key, 0, i−1) (find insert spot)   shift A[pos..i−1] right by one   A[pos] = key

Binary Search (often called "binary sort")

Finds an item in a SORTED array by checking the middle and discarding half each time. Best: O(1) (middle item). Average: O(log n). Worst: O(log n). Recurrence: T(n) = T(n/2) + 1.

Heap

A binary tree stored in an array that is "complete" (filled left to right). Max-heap: every parent ≥ its children (max at root). Min-heap: every parent ≤ children (min at root). For index i: parent = (i−1)/2, left child = 2i+1, right child = 2i+2. Height = O(log n).

Heap: runtimes

Peek at max/min: O(1). Insert: Best O(1), Average O(1) (random data), Worst O(log n). Extract max/min: O(log n) in all cases. Build Heap from an array: O(n). Heapsort: Best/Avg/Worst O(n log n), space O(1), not stable.

Heap: pseudocode (Insert and Extract)

Insert(H, x): add x at the end of the array; BubbleUp(H, last index). ExtractMax(H): save H[0]; move the last item to the root; shrink heap by 1; BubbleDown(H, 0); return the saved item. BuildHeap(A): for i = n/2 − 1 down to 0: BubbleDown(A, i). HeapSort(A): BuildHeap(A); repeat: swap root with last item, shrink heap, BubbleDown(A, 0).

Bubble-Up (Sift-Up)

Heap operation: move a new item UP the tree, swapping with its parent while it is bigger than the parent (max-heap). Best: O(1) (already in place). Average: O(1). Worst: O(log n) (travels to the root).

Bubble-Down (Sift-Down)

Heap operation: move an item DOWN the tree, swapping with its LARGER child while a child is bigger (max-heap). Best: O(1) (already in place). Average: O(log n). Worst: O(log n) (travels to a leaf).

Bubble Sort (in case "Bubble-Up/Down Sort" means this)

Repeatedly step through the list, swapping adjacent items that are out of order, so big items "bubble" to the end. Best: O(n) (already sorted, with an early-exit flag). Average: O(n²). Worst: O(n²). Space: O(1). Stable.

Rules of Thumb for Big-O

Rules of thumb: one loop = O(n); nested loops = O(n²); halving the problem each step = O(log n); loop with a halving step inside = O(n log n).

Bubble Sort Pseudocode

Pseudocode: BubbleSort(A): for i = 0 to n−2: swapped = false; for j = 0 to n−2−i: if A[j] > A[j+1]: swap them; swapped = true; if not swapped: st

Bubble Down Pseudocode

BubbleDown(H, i): loop: l = 2i+1; r = 2i+2; largest = i; if l < size and H[l] > H[largest]: largest = l; if r < size and H[r] > H[largest]: largest = r; if largest == i: stop; swap H[i], H[largest]; i = largest.

Bubble Up Pseudocode

BubbleUp(H, i): while i > 0 and H[i] > H[parent(i)]: swap H[i], H[parent(i)]; i = parent(i).

Binary Sort Pseudocode

BinarySearch(A, x): low = 0; high = n−1; while low ≤ high: mid = (low+high)/2; if A[mid] == x return mid; else if A[mid] < x low = mid+1; else high = mid−1; return not found.