0
$\begingroup$

If we have a function $f(x) = 6x^4 - 2x^3 + 5$ and that function is $\mathcal{O}(x^4)$. Does that mean that it will also be $\Omega(x^4)$ and consequently $\Theta(x^4)$?

$\endgroup$
0

3 Answers 3

4
$\begingroup$

Presumably you're talking about $x \to \infty$. Then it is true that $f(x) = \mathcal O(x^4)$ and that $f(x) = \Omega(x^4)$, so $f(x) = \Theta(x^4)$. However, it's not always true that a function that is $\mathcal O(x^4)$ is also $\Omega(x^4)$. For example, $x^3 = \mathcal O(x^4)$, but not $\Omega(x^4)$.

$\endgroup$
1
$\begingroup$

In terms of $x\to\infty$, you have that a function $f$ is $\Theta(g)$ if it is $\mathcal O(g)$ and $\Omega(g)$ per definition, so you definitely have the inverse of your statement.

Coincidentally, the function you described is $\Theta(x^4)$ anyway. However, it is not always the case that $f\in\mathcal O(g)$ implies $f\in\Theta(g)$.

You can heuristically read $\Theta$ as "equals", $\mathcal O$ as less or equal than and $\Omega$ as greater or equal then.

As an example, you have e.g. that $1\in\mathcal O(x^4)$ but not $1\in\Omega(x^4)$, thus $1\not\in\Theta(x^4)$.

$\endgroup$
0
$\begingroup$

For your specific example, yes. In general: No.

Informally put: Let $f: \mathbb{R^+} \mapsto \mathbb{R}^+$ and $g: \mathbb{Z} \mapsto \mathbb{R}^+$ be two positive real-valued functions whose domain is the set of positive reals.

  1. Then $g$ is $O(f)$ iff there are constant $c>0$ such that $g(x) \le c \times f(x)$ for all $x$.

  2. Then $g$ is $\Omega(f)$ iff there is a constant $c'>0$ such that $g(x) > c' \times f(x)$ for all $x$.

  3. Then $g$ is $\theta(f)$ iff BOTH $g$ is $O(f)$ AND $g$ is $\Omega(f()$.

  4. If $g$ is $O(f)$ but not $\Omega(f)$ then $g$ is $o(f)$,

  5. If $g$ is $\Omega(f)$ but not $O(f)$ then $g$ is $\omega(f)$.

Now letting $f$ be as in your question and $g = x^4$ indeed $g$ is both $\Omega(f)$ and $g$ is $O(f)$, so $g$ is indeed $\theta(f)$. But this follows becasue $f$ and $g$ are both polynomials of the same degree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .