CPSC 121 Study Guide - Final Guide: Binary Logarithm, Binary Search Algorithm, Mathematical Induction
38
CPSC 121 Full Course Notes
Verified Note
38 documents
Document Summary
Prove that every positive integer n greater than 1 can be written as a product of primes. Proof: we prove the result by induction on n. We can write n = n and n is a product of primes. Suppose that every value from 2 to n - 1 is a product of primes (ih) We can write n = a * b where. By the inductive hypothesis (ih) a = p1 * p2 * * pn where pi is prime. = p1 * p2 * * pm where qi is prime. Then n = a * b = p1 * p2 * pn * q1 * q2 * * qn. Hence by the principle of m. i. , every positive integer larger than 1 can be written as a product of primes. Prove that binary search makes at most [log2 (size+1)] comparisons if size => 1.
