CHEM 131 Midterm: Exam 2b No Solutions Spring 1996

• School: University of Maryland
• Department: Chemistry and Biochemistry
• Course: CHEM 131
• Professor: All

Document Summary

I agree to complete this exam without unau- thorized assistance from any person, mate- rials, or device. 1 problem 1 (10 points: each subproblem is 2 points) For each statement below state if it is true or false: let f, g be two positive functions. If f (n) = (n) and g(n) = (n) then. |f (n/3) g(n)| = (n). true false: let f, g be two positive functions. If f (n) = o(g(n)) and h(n) = (g(n)) then f (n) = o(h(n)). true false: log3(n) = (log5(n)). true false, n2| sin n| = (n2). true false, n2 + (log(n)) n. 2 problem 2 (20 points; each subproblem is 10 points) Give asymptotic upper bounds for the following recurrences. You can use master theorem, when it is applicable. Assume that t (1) = 1: t (n) = 9t (n/3) + n log(n, t (n) = 2t (n/4) + n.