# Definition:Order Notation

## Definition

### $O$-Notation

**$\OO$ notation** is a type of order notation, typically used in computer science for comparing 'run-times' of algorithms, or in analysis for comparing growth rates between two growth functions.

### $\Theta$-Notation

**Big-theta notation** is a type of order notation for typically comparing 'run-times' or growth rates between two growth functions.

Big-theta is a stronger statement than big-O and big-omega.

Suppose $f: \N \to \R, g: \N \to \R$ are two functions.

Then:

- $\map f n \in \map \Theta {\map g n}$

- $\paren {\map f n \in \map \OO {\map g n} } \land \paren {\map f n \in \map \Omega {\map g n} }$

where $\map \OO {\map g n}$ is big-O and $\map \Omega {\map g n}$ is big-omega.

This is read as:

- $\map f n$ is
**big-theta**of $\map g n$.

### $\theta$-Notation

### $\Omega$-Notation

**Big-Omega notation** is a type of order notation for typically comparing 'run-times' or growth rates between two growth functions.

Let $f, g$ be two functions.

Then:

- $\map f n \in \map \Omega {\map g n}$

- $\exists c > 0, k \ge 0: \forall n > k: \map f n \ge c \map g n$

This is read as:

**$\map f n$ is big omega of $\map g n$**.

### $\omega$-Notation

Let $f$ and $g$ be real functions.

Then:

- $\map f n \in \map \omega {\map g n}$

is equivalent to:

- $\ds \lim_{n \mathop \to \infty} {\frac {\map f n} {\map g n} } = \infty$

## Sources

- 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**order notation**