 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2003/functional-programming-data-structures-and-algorithms-procedural-programming-and-digital-hardware/4/b/solution

For eventually nonnegative functions

T, f, g

T \in O (f) ⟺ \exists C > 0 \exists n_{0} \forall n \geq n_{0} : 0 \leq T (n) \leq C f (n),

T \in Ω (g) ⟺ \exists c > 0 \exists n_{0} \forall n \geq n_{0} : 0 \leq c g (n) \leq T (n) .

These are asymptotic upper bounds and lower bounds up to positive constant factors. The notation

T (n) = O (f (n))

conventionally expresses membership in the class

O (f)

, rather than equality of two numerical functions.

 New to topics? Read the docs here!