 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/a/solution

For these real-valued functions, $f (n) = O (g (n))$ means that there exist constants

C > 0

and

N \in N

such that

∣ f (n) ∣ \leq C ∣ g (n) ∣ for every n \geq N .

The absolute values matter because neither function is assumed nonnegative. The constants are independent of

n

; finitely many earlier values do not affect Big O notation.

 New to topics? Read the docs here!