CSC165H1 : Summer.2012.e7_solutions.pdf

• School: UTSG
• Department: Computer Science
• Course: CSC165H1
• Professor: Nathalie Fournier

Document Summary

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: 2n4 6n3 + 34 is o((100n 5)3). Let n0 be (cid:100)106c(cid:101) + b + 6. 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: 2n4 6n3 + 34 is o(n4 n + 2). Assume n n and n 3. Then, 2n4 6n3 + 34 (cid:54) 2n4 6n3 + 81 (cid:54) 2n4 6n3 + n4. = 3n4 6n3 = 3(n4 2n3) (cid:54) 3(n4 n) (cid:54) 3(n4 n + 2) Since n 1, so 2n3 n. So, n n, n 3 2n4 6n3 + 34 (cid:54) 3(n4 n + 2)