Big-Theta, Big-O, Big-Omega in $\Bbb{R}^n$.

69 Views Asked by At

Is the following statement true?

Let $ g : \Bbb{R}^n \to \Bbb{R}^n $ $$ \Theta_{(g)} = \Omega_{(g)} \cap O_{(g)} $$

1

There are 1 best solutions below

1
On BEST ANSWER

The notation $f(n)=O(g(n))$ means that $|f|$ is bounded above by $g$ asymptotically. Formally, $$ \exists k>0\quad\exists n_0 \in \mathbb{N}\quad\forall n\in\mathbb{N}, n>n_0:\quad|f(n)|\leq k\cdot g(n). $$ Note that this implies that $f$ is also bounded above by $g$ asymptotically.

The notation $f(n)=\Omega(g(n))$ means that $f$ is bounded below by $g$ asymptotically. Formally, $$ \exists k>0\quad\exists n_0\in\mathbb{N}\quad\forall n\in\mathbb{N},n>n_0:\quad f(n)\geq k\cdot g(n). $$ The notation $f(n)=\Theta(g(n))$ means that $f$ is bounded both above and below by $g$ asymptotically. Formally, $$ \exists k_1>0\quad\exists k_2>0\quad\exists n_0\in\mathbb{N}\quad\forall n\in\mathbb{N}, n>n_{0}:\quad k_1\cdot g(n)\leq f(n)\leq k_2\cdot g(n). $$ Note that if $f(n)=\Theta(g(n))$, then both $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ hold, which means that

$$ \Theta(g(n)) = O(g(n)) \cap \Omega(g(n)), $$

by definition.