Runtime

Absolutely Dominated

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is absolutely dominated by

f

iff for all

n \in N_{0}, g (n) \leq f (n)

Squared Dominates Linear

Let

f (n) = n^{2}

and

g (n) = n

show that

g

is absolutely dominated by

f

Absolutely Dominated up to a Constant Factor

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is absolutely dominated up to a constant factor by

f

iff there exists

c \in R^{+}

such that

g

is absolutely dominated by

c f

Eventually Dominated

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is eventually dominated by

f

iff there exists some

n_{0} \in R^{+}

such that

\forall n \in N^{+}, n \geq n_{0}

then we know

g (n) \leq f (n)

Lower Degree Polynomial plus Constant is Eventually Dominated by Higher Degree

Let

f (n) = n^{2}

and

g (n) = n + 90

Eventually Dominated up to a Constant Factor

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is eventually dominated by

f

iff there exists some

c \in R^{+}

such that

g

is eventually dominated by

c f

Big-O

Suppose we have

f : N_{0} \to R^{\geq 0}

, then we define the set

O (f)

as all functions that are eventually dominated up to a constant factor by

f

Big-O of

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is big-o of

f

iff

g \in O (f)

Note that if $g$ is big-o of $f$ , then we know that $f$ is an asymptotic upper bound for $g$

Basic Polynomial

Suppose

f (n) = n^{3}

and

g (n) = n^{3} + 100 n + 5000

, show that

g \in O (f)

TODO

Omega

Suppose we have

f : N_{0} \to R^{\geq 0}

, then we define the set

Ω (f)

as the set of all functions

g : N_{0} \to R^{\geq 0}

such that

\exists c, n_{0} \in R^{+} s.t. \forall n \in N_{0}, n \geq n_{0} ⟹ g (n) \geq c \cdot f (n)

Omega of

Let

f, g : N_{0} \to R^{\geq 0}

, we say that

g

is omega of

f

iff

g \in Ω (f)

Here we can think of $Ω$ as being $O$ 's counter part, so that when $g$ is omega of $f$ , then $f$ is a lower bound on $g$ 's eventual growth rate.

Theta

Suppose we have

f : N_{0} \to R^{\geq 0}

, then we define the set

Θ (f)

as the set of all functions

g : N_{0} \to R^{\geq 0}

such that

g \in O (f) \cap Ω (f)

where we are using big-o and theta

The point of theta is to say that $g$ is both eventually upper and lower bounded by $f$ which means that $g$ should grow asymptotically the same as $f$