 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/discrete-mathematics-continuous-mathematics-and-probability/3/b/iv/solution

False. The sum of squares of the first n positive integers gives

\frac{1}{n ^{2}} \sum_{k = 1}^{n} k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6 n ^{2}} \geq \frac{n}{3} .

This ratio is unbounded, so it cannot satisfy the constant bound required by Big O notation. In fact the sum has order

n^{3}

, as its leading term also shows.

 New to topics? Read the docs here!