false

Class Notes
(838,240)

Canada
(510,788)

University of Toronto St. George
(44,093)

Computer Science
(754)

CSC165H1
(167)

Nathalie Fournier
(31)

Lecture

Unlock Document

Computer Science

CSC165H1

Nathalie Fournier

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.