Welcome to our community

Be a part of something great, join today!

A question regarding Big Theta notation

jamesriechel

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

New member
Feb 2, 2014
8
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!
 
Last edited:

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502

jamesriechel

New member
Feb 2, 2014
8
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502