 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/2/b/iii/solution

Divide by the proposed comparison function

2^{n}

\frac{n ^{2} + n 2 ^{n}}{2 ^{n}} = \frac{n ^{2}}{2 ^{n}} + n \geq n .

False: n^{2} + n 2^{n} \neq = O (2^{n}) .

 New to topics? Read the docs here!