Study Guides (248,297)
CSC165H1 (27)

# Summer.2012.e7_solutions.pdf

2 Pages
139 Views

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

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

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.