A question regarding Big Theta notation

[jamesriechel]

If f(x) if big-theta of g(x), is it also always the case then that g(x) is big-theta of f(x)?

I'm brand new to this website, and couldn't figure out how to start a new thread, but I also have a question about Big Theta notation.

Is big-theta(x/y) = big-theta(x)/big-theta(y)?

I know big-o(x/y) = big-o(x)/big-o(y), but I don't know if big-omega(x/y) = big-omega(x)/big-omega(y).

I can attempt to prove the latter, but I was hoping somebody already knows.

Thanks!
-James

 

[Evgeny.Makarov]

Re: Growth of Functions - Big Theta

Welcome to the forum!

and couldn't figure out how to start a new thread

To start a new thread, go to an appropriate subforum, for example, 'Discrete Mathematics, Set Theory, and Logic" (to see the list of subforums click the big "Forums" tab at the top of the page) and click the "+ Post New Thread" button. The button is brown and is located at the top, right above the name of the subforum.

I also have a question about Big Theta notation. Is big-theta(x/y) = big-theta(x)/big-theta(y)?

What do you mean by $\Theta(x)/\Theta(y)$?

 

[jamesriechel]

Re: Growth of Functions - Big Theta

Welcome to the forum!

To start a new thread, go to an appropriate subforum, for example, 'Discrete Mathematics, Set Theory, and Logic" (to see the list of subforums click the big "Forums" tab at the top of the page) and click the "+ Post New Thread" button. The button is brown and is located at the top, right above the name of the subforum.

What do you mean by $\Theta(x)/\Theta(y)$?

Yes, my question is: Does $\Theta(x/y) = \Theta(x)/\Theta(y)$?

Or, more generally: Does $\Theta(f(x)/g(y)) = \Theta(f(x))/\Theta(g(y))$?

Thanks!

 

[Evgeny.Makarov]

Re: Growth of Functions - Big Theta

Yes, my question is: Does $\Theta(x/y) = \Theta(x)/\Theta(y)$

OK, but what do you mean by $\Theta(x)/\Theta(y)$? Do you realize that $\Theta(g(x))$ is at best a set of functions, and at worst a part of the notation $f(x)=\Theta(g(x))$ that cannot be broken? How do you divide two sets of functions?

 

[jamesriechel]

Re: Growth of Functions - Big Theta

OK, but what do you mean by $\Theta(x)/\Theta(y)$? Do you realize that $\Theta(g(x))$ is at best a set of functions, and at worst a part of the notation $f(x)=\Theta(g(x))$ that cannot be broken? How do you divide two sets of functions?

Ok, I think I've got it worked out. For my research, there's three $f(x)$'s and $g(y)$'s I am specifically interested in. In each case, I want to show $\Theta(f(x))/\Theta(g(y)) = \Theta(f(x)/g(y))$. I think I have done this. Here's my reasoning in each case. $x$ and $y$ are variables, not functions.

Case 1: $f(x) = x, g(y) = y$

$\Theta(x)/\Theta(y) = x/y = \Theta(x/y)$

Case 2: $f(x) = \sqrt{x}, g(y) = \sqrt{y}$

$\Theta(\sqrt{x})/\Theta(\sqrt{y}) = \sqrt{x}/\sqrt{y} = \sqrt{x/y} = \Theta(\sqrt{x/y})$

Case 3: $f(x) = \lg x, g(x, y) = \lg \frac{x}{y}$

$\Theta(\lg x)/\Theta(\lg \frac{x}{y}) = \lg x / \lg \frac{x}{y} = \frac{\lg x}{\lg x - \lg y} = \Theta(\frac{\lg x}{\lg x - \lg y})$

Thanks!
-James

 

[Evgeny.Makarov]

Not only your reasoning, but also the claim you are trying to prove does not make sense to me. I can't help you until you say what you mean by $\Theta(f(x))/\Theta(g(y))$. (I am saying this for the third time.) This expression makes as little sense as $\sqrt{}/\lg$.

 

[jamesriechel]

Not only your reasoning, but also the claim you are trying to prove does not make sense to me. I can't help you until you say what you mean by $\Theta(f(x))/\Theta(g(y))$. (I am saying this for the third time.) This expression makes as little sense as $\sqrt{}/\lg$.

I have to leave town, and will reply in greater detail when I return, but...

I disagree that $\Theta(x)$ is a set of functions. Looking at the definition of $\Theta$-notation:

$\Theta(x) = x$

because:

$c_1 x \leq x \leq c_2 x$

Thanks!
-James

 

[Evgeny.Makarov]

Looking at the definition of $\Theta$-notation:

$\Theta(x) = x$

because:

$c_1 x \leq x \leq c_2 x$

This is not correct. You can find the definition of big-O notation in Wikipedia here and of other similar notations here. The important thing is that $f(x)=O(g(x))$, or $f(x)\in O(g(x))$, is an atomic notation, meaning that it should be taken as a whole and its parts don't have a separate meaning. It does not mean that there is a function $O(g(x))$ that is equal to $f(x)$. Rather, it is an unbreakable propositions, i.e., something that is either true or false for given functions $f(x)$ and $g(x)$. The same is true for other similar notations, including Ω. See also the discussion on $=$ vs $\in$ here.

 

[jamesriechel]

This is not correct. You can find the definition of big-O notation in Wikipedia here and of other similar notations here. The important thing is that $f(x)=O(g(x))$, or $f(x)\in O(g(x))$, is an atomic notation, meaning that it should be taken as a whole and its parts don't have a separate meaning. It does not mean that there is a function $O(g(x))$ that is equal to $f(x)$. Rather, it is an unbreakable propositions, i.e., something that is either true or false for given functions $f(x)$ and $g(x)$. The same is true for other similar notations, including Ω. See also the discussion on $=$ vs $\in$ here.

It's true: my notation was sloppy. I apologize. I'm still out of town, but am working on the nitty gritty mathematics. Nothing I want to share yet. But I have a stupid question :

If $a(x) = \Theta(f(x))$, and $b(y) = \Theta(g(y))$, is $a(x)/b(y) = \Theta(f(x)/g(y))$?

Thanks!
-James

 

[Evgeny.Makarov]

If $a(x) = \Theta(f(x))$, and $b(y) = \Theta(g(y))$, is $a(x)/b(y) = \Theta(f(x)/g(y))$?

I assume you are considering functions that depend on the same variable and not some functions dependent on $x$ and others dependent on $y$. As is it, $a(x)/b(y)$ is a function of both $x$ and $y$, and Θ requires an extension of the original definition for multi-variable case. If you insist on considering several variables, please say so.

Yes, if $g(x)$ is eventually positive, then from
\[
\begin{aligned}
c_1f(x)&\le a(x)\le C_1f(x)\\
c_2g(x)&\le b(x)\le C_2(x)
\end{aligned}
\]
we get
\[
\frac{c_1f(x)}{C_2g(x)}\le \frac{a(x)}{b(x)}\le \frac{C_1f(x)}{c_2g(x)}
\]
At least according to the definition of Θ in Wikipedia, $c_2$ and $C_2$ are positive, so division makes sense.

 

[jamesriechel]

I assume you are considering functions that depend on the same variable and not some functions dependent on $x$ and others dependent on $y$. As is it, $a(x)/b(y)$ is a function of both $x$ and $y$, and Θ requires an extension of the original definition for multi-variable case. If you insist on considering several variables, please say so.

Yes, if $g(x)$ is eventually positive, then from
\[
\begin{aligned}
c_1f(x)&\le a(x)\le C_1f(x)\\
c_2g(x)&\le b(x)\le C_2(x)
\end{aligned}
\]
we get
\[
\frac{c_1f(x)}{C_2g(x)}\le \frac{a(x)}{b(x)}\le \frac{C_1f(x)}{c_2g(x)}
\]
At least according to the definition of Θ in Wikipedia, $c_2$ and $C_2$ are positive, so division makes sense.

Thanks! (How do I "thank" you for your help here in this thread?)

I went back to the original mathematics, and proved the four (4) $\Theta$-notations in four (4) long proofs. I don't want to type them in here. It'll take too long.

Three (3) of the proofs produced the expected result. One (1) produced a slightly different and surprising result.

I can give one sample proof, if you want, that doesn't start with $\Theta$ notation, but ends there as a final result. Let me know if you want a peek.

Thanks!
-James

 

[Evgeny.Makarov]

How do I "thank" you for your help here in this thread?

Click the "Thanks" link in the bottom-right corner of a post.

 

[jamesriechel]

Click the "Thanks" link in the bottom-right corner of a post.

Hi again! Only one (1) of my four (4) proofs produces a result in two (2) variables. I know that:

$f(x) = \Theta(f(x))$

In my one proof, I get:

$S_k = \frac{\log (n + 1)}{\log (n + k) - \log k}$

Can I say:

$S_k = \Theta[\frac{\log (n + 1)}{\log (n + k) - \log k}]$

?

Thanks!
-James

 

[Evgeny.Makarov]

$S_k = \frac{\log (n + 1)}{\log (n + k) - \log k}$

Can I say:

$S_k = \Theta[\frac{\log (n + 1)}{\log (n + k) - \log k}]$

?

Yes.

 

[jamesriechel]

Yes.

Thanks!

-James