Study Guides (256,439)
CA (124,651)
UTSG (8,518)
CSC (188)
CSC165H1 (27)

# Summer.2012.e7_solutions.pdf

2 Pages
139 Views

Department
Computer Science
Course Code
CSC165H1
Professor
Nathalie Fournier

This preview shows half of the first page. Sign up to view the full 2 pages of the document.
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

#### Loved by over 2.2 million students

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
Description
CSC165H1Y 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. 2n â–¯ 6n + 34 is O((100n â–¯ 5) ): This is false. Assume c 2 R , B 2 N Let n 0e d10 ce + B + 6 Then n 0 N Then n â–¯ B 0 Then 2n â–¯06n + 30 > 2n â–¯ 6n 3 0 0 > 2n â–¯ n 4 Since n â–¯ 6 0 0 0 = n = (d10 ce + B + 6)n 3 0 0 6 3 > 10 cn 0 3 > c(100n 0 3 > c(100n 0 5) 4 3 3 Then 9n 2 N;n â–¯ B ^ 2n â–¯ 6n + 34 > c(100n â–¯ 5) + 4 3 3 Then, 8c 2 R ;8B 2 N;9n 2 N;n â–¯ B ^ 2n â–¯ 6n + 34 > c(100n â–¯ 5) . So, 2n â–¯ 6n + 34 2 = O((100n â–¯ 5) )3 4 3 4 2. 2n â–¯ 6n + 34 is O(n â–¯ n + 2): This is true. Assume n 2 N and n â–¯ 3 4 3 Then, 2n â–¯ 6n + 34 4 3 6 2n â–¯ 6n + 81 4 3 4 4 6 2n â–¯ 6n + n Since 81 = 3 and n â–¯ 3 = 3n â–¯ 6n = 3(n â–¯ 2n ) 3 6 3(n â–¯ n) Since n â–¯ 1, so
More Less

Only half of the first page are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document
Notes
Practice
Earn
Me

OR

Don't have an account?

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.