Class Notes (838,240)
CSC165H1 (167)
Lecture

# tut06solution.pdf

2 Pages
85 Views

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1F Tutorial # 6 | Sample Solutions Fall 2011 4 2 5 3 1. Write a detailed structured proof that 5n ▯ 3n + 1 2 O(6n ▯ 4n + 2n): Proof outline: By de▯nition of \O", we have to show + 4 2 5 3 9c 2 R ;9B 2 N;8n 2 N;n > B ) 5n ▯ 3n + 1 6 c(6n ▯ 4n + 2n): This can be done using the following proof structure. Let c = ::: Then c 2 R . + Let B = ::: Then B 2 N. 0 0 Assume n 2 N and n > B . ...show that 5n ▯ 3n + 1 6 c (6n ▯ 4n + 2n)... Then 8n 2 N;n > B ) 5n ▯ 3n + 1 6 c (6n ▯ 4n + 2n).5 3 + 4 2 5 3 Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) 5n ▯ 3n + 1 6 c(6n ▯ 4n + 2n). Scratch work: Working \forward" from the left-hand side, we get: 4 2 4 5n ▯ 3n + 1 6 5n + 1 4 4 6 5n + n if n > 1 4 6 6n 6 n ▯ n4 if n > 6 6 n 5 (Note that there are other inequalities we could have reached, e.g., 6n 6 6n for all n > 1.) Working \backward" from the right-hand side, we get: 5 3 5 3 6n ▯ 4n + 2n > 6n ▯ 4n 5 5 3 5 > 6n ▯ 4n because ▯n > ▯n 5 > 2n > n 5 Since both chains of inequalities connect, we are done: we can pick B = 6 (because we require n > 6 in our ▯rst chain) and c = 1. 0 0 Proof: (This is the actual ▯nal \solution". We skip the formal introduction of B and c and instead, simply use their values directly. This style of proof is ▯ne, and it is a little less 0 0 verbose than using \B " and \c " throughout the argument.) Assume n 2 N and n > 6. Then, 5n ▯ 3n + 1 6 5n + 1 4 6 5n + n 4 since n > 6 > 1 4 6 6n 4 6 n ▯ n since n > 6 5 6 2n 6 6n ▯ 4n 5 6 6n ▯ 4n 3 since ▯n 6 ▯n 3 6 6n ▯ 4n + 2n: Then 8n 2 N;n > 6 ) 5n ▯ 3n + 1 6 6n ▯ 4n + 2n.5 3 + 4 2 5 3 Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) 5n ▯ 3n + 1 6 c(6n ▯ 4n + 2n). # pick B = 6 and c = 1 Then 5n ▯ 3n + 1 2 O(6n ▯ 4n + 2n), by de▯nition. Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 2 CSC165H1F Tutorial # 6 | Sample Solutions Fall 2011 5 3 4 2 2. Write a detailed structured proof that 6n ▯ 4n + 2n 2 = O(5n ▯ 3n + 1): Proof ou
More Less

Related notes for CSC165H1
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.