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

The Big O notation asserts an eventual uniform bound on the size of

f

by a constant multiple of the size of

g

f (n) = O (g (n)) ⟺ \exists C > 0 \exists n_{0} \forall n \geq n_{0} : ∣ f (n) ∣ \leq C ∣ g (n) ∣.

C, n_{0}

may depend on the two functions but cannot depend on

n

. Absolute values matter because the stated functions can be real-valued with either sign.

 New to topics? Read the docs here!