Department

Computer Science

Course Code

CSC165H1

Professor

Nathalie Fournier

CSC 165 H1Y Homework Exercise # 7 â€“ Sample solutions Summer 2012

Worth: 3% Due: By 3 pm on Tuesday July 31.

Determine whether each of the following statements is true. Write a detailed structured proof to prove or

disprove the statement.

1. 2n4âˆ’6n3+ 34 is O((100nâˆ’5)3).

This is false.

Assume câˆˆR+,BâˆˆN

Let n0be d106ce+B+ 6

Then n0âˆˆN

Then n0â‰¥B

Then 2n4

0âˆ’6n3

0+ 34

>2n4

0âˆ’6n3

0

>2n4

0âˆ’n4

0Since n0â‰¥6

=n4

0= (d106ce+B+ 6)n3

0

>106cn3

0

>c(100n0)3

>c(100n0âˆ’5)3

Then âˆƒnâˆˆN, n â‰¥Bâˆ§2n4âˆ’6n3+ 34 > c(100nâˆ’5)3

Then, âˆ€câˆˆR+,âˆ€BâˆˆN,âˆƒnâˆˆN, n â‰¥Bâˆ§2n4âˆ’6n3+ 34 > c(100nâˆ’5)3.

So, 2n4âˆ’6n3+ 34 /âˆˆ O((100nâˆ’5)3)

2. 2n4âˆ’6n3+ 34 is O(n4âˆ’n+ 2).

This is true.

Assume nâˆˆNand nâ‰¥3

Then, 2n4âˆ’6n3+ 34

62n4âˆ’6n3+ 81

62n4âˆ’6n3+n4Since 81 = 34and nâ‰¥3

= 3n4âˆ’6n3= 3(n4âˆ’2n3)

63(n4âˆ’n) Since nâ‰¥1, so âˆ’2n3â‰¤ âˆ’n

63(n4âˆ’n+ 2)

So, âˆ€nâˆˆN, n â‰¥3â‡’2n4âˆ’6n3+ 34 63(n4âˆ’n+ 2)

So, âˆƒcâˆˆR+,âˆƒBâˆˆN,âˆ€nâˆˆN, n â‰¥Bâ‡’2n4âˆ’6n3+ 34 6c(n4âˆ’n+ 2)

(Since 3 âˆˆNand 3 âˆˆR+, take c= 3 and B= 3)

So, 2n4âˆ’6n3+ 34 âˆˆ O(n4âˆ’n+ 2)

Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 2

Over 90% improved by at least one letter grade.

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah â€” University of Toronto

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim â€” University of Michigan

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna â€” University of Wisconsin

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne â€” University of California

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

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.

Add your courses

Get notes from the top students in your class.