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

Table of contents
- Solution 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.

 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