Class Notes (838,006)
Canada (510,619)
CSC104H1 (67)

Lecture 21, 22 - Algorithm Complexity

3 Pages
Unlock Document

Computer Science
Mark Lanctot

Algorithm Complexity – Lecture 21/22 Recall linkedlist.c append operation. Because a pointer to end of list is kept as tail, statements -> time is O(1) Induction proofs Induction is used when you have a claim that some property holds for all n >= 0 or 1, where n is an integer. Call this claim P(n) Two steps: 1. Prove base case – claim holds for n = 0 or n = 1 2. Show that P(n) implies P(n+1). Assume that P(n) is true, and prove that P(n+1). a. Establishes an infinite implication… (-> means implies) b. P(n) -> P(1) -> P(2) -> P(3) Example 1: P(n) =∑ Step 1 - Base case: N = 1 ∑ Step 2 – Assume that P(n) is true. Show that P(n+1) is true ∑ = . Example 2: ∑ Step 1 – Base Case: N = 1∑ Step 2 – Assume that P(n) is true. Prove for P(n+1) ∑ ∑ Example 3 3 P(n) is n >= 2, then p – n is divisible by 3 Step 1 – Base Case P(2) and 6 is divisible by 3. Step 2 Assume that P(n) is true -> n – n = 3r. r is some integer. Prove P(n+1) P(n) is true because this is divisible by 3. Induction assumed here. Applications for Algorithms – Breadth First Search on a Grid Start End Two lists: C , null ) Line above is Tuple representing coordinates (row/column) App
More Less

Related notes for CSC104H1

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.