Definition:Big-Omega
Definition
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.
Domain and range of $f$ and $g$ to be specified: reals?
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this point in more detail, feel free to use the talk page.
If you are able to explain it, then when you have done so you can remove this instance of {{Explain}} from the code.
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$.
Put the below into separate pages, either as a 2nd definition or just an equivalence proof
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Another method of determining the condition is the following limit:
- $\ds \lim_{n \mathop \to \infty} {\frac {\map f n} {\map g n} } = c > 0$
where $0 < c \le \infty$.
If such a $c$ does exist, then:
- $\map f n \in \map \Omega {\map g n}$
The below into its own page
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
To say that $\map f n \in \map \Omega {\map g n}$ is equivalent to:
- $\map g n \in \map \OO {\map f n}$
where $\OO$ is the big-O notation.