Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 3 / b

Table of contents
- i b
  - Solution i
- ii b
  - Solution ii

i

Solution

Choose constants

C_{1}, C_{2} > 0

and a common threshold beyond which

f_{1} \leq C_{1} g_{1}

and

f_{2} \leq C_{2} g_{2}

. Positivity permits multiplication:

∣ f_{1} f_{2} ∣ = f_{1} f_{2} \leq C_{1} C_{2} g_{1} g_{2} .

The fixed constant

C_{1} C_{2}

proves $f_{1} f_{2} = O (g_{1} g_{2})$ by the definition of big O notation.

ii

Solution

Beyond the same common threshold, the triangle inequality gives

∣ f_{1} - f_{2} ∣ \leq f_{1} + f_{2} \leq C_{1} g_{1} + C_{2} g_{2} \leq max (C_{1}, C_{2}) (g_{1} + g_{2}) .

Thus $f_{1} - f_{2} = O (g_{1} + g_{2})$ . The absolute value matters because the difference need not itself be positive, even though the four original functions are.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version