Category:Definitions/Order Notation

From ProofWiki
Jump to navigation Jump to search

This category contains definitions related to Order Notation.
Related results can be found in Category: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}$

if and only if:

$\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

Definition:Little-Theta

$\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}$

if and only if:

$\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

Subcategories

This category has the following 2 subcategories, out of 2 total.

D

O