Big Theta equivalence classes and proofs I have a series of equation and I need to find which are in the same big theta equivalence class and order them. I am super confused by big theta. The equations are:


*

*$\ln(2x)$

*$\ln(x)$

*$x^2+2x$

*$7x^2-x+100$

*$\ln(x^3)$

*$\log_2(x)$

*$x\ln(x)$

*$x\ln(x^2+2x)$

*$x\ln(\ln(x))$

 A: Recall that $f(x) = \Theta\bigl(g(x)\bigr)$ if there exist constants $c_1$, $c_2 > 0$ such that for all $x$ sufficiently large, we have
$$c_1 g(x) \leq f(x) \leq c_2 g(x). \tag*{(1)}$$
I'll illustrate this with a couple of the examples that you've given.
First, $\ln(2x) = \Theta\bigl(\ln(x)\bigr)$. To see why, first recall that $\ln(2x) = \ln(x) + \ln(2)$.  So,
$$\lim_{x \to \infty} \dfrac{\ln(2x)}{\ln(x)} = \dfrac{\ln(x) + \ln(2)}{\ln(x)} = 1.$$
So, we could take $c_1 = 1/2$ and $c_2 = 3/2$  in $(1)$.  Thus, $\ln(2x) = \Theta\bigl(\ln(x)\bigr)$.  This also means that $\ln(x) = \Theta\bigl(\ln(2x)\bigr)$ (do you see why?).
Second, $\ln(x) \neq \Theta(x^2 + 2x)$.  This is because, for all $c > 0$, for $x$ sufficiently large we have $\ln(x) \leq c(x^2 + 2x)$.  To see this, simply observe that
$$\lim_{x \to \infty} \dfrac{\ln(x)}{x^2 + 2x} = 0.$$
Thus, there does not exist a constant $c_1$ such that the first inequality in $(1)$ holds, and we have $\ln(x) \neq \Theta(x^2 + 2x)$.
These are examples of the principle that, for nonnegative functions $f$ and $g$, $f(x) = \Theta\bigl(g(x)\bigr)$ if $\lim_{x \to \infty} f(x)/g(x)$ exists and is strictly between $0$ and $\infty$, while $f(x) \neq \Theta\bigl(g(x)\bigr)$ if $\lim_{x \to \infty} f(x)/g(x) = 0$ or $\lim_{x \to \infty} f(x)/g(x) = \infty$.
A: One thing to notice
is that
big-theta is an equivalence relation,
while
big-O and little-o are not.
In other words,
if $f(x) = \Theta\bigl(g(x)\bigr)$,
and $g(x) = \Theta\bigl(h(x)\bigr)$,
then
$f(x) = \Theta\bigl(f(x)\bigr)$,
$g(x) = \Theta\bigl(f(x)\bigr)$,
and
$f(x) = \Theta\bigl(h(x)\bigr)$.
To show that big-O is not an
equivalence relation,
we only need one counterexample.
Just note that,
as $x \to \infty$,
$x = O(x^2)$
but $x^2 \not = O(x)$.
A general principle
which you should get comfortable with
is
if $f(x) = O(g(x))$ then
$g(x)+f(x) = \Theta(g(x))$.
Some particular results you should know
(and know why they are true)
are,
if $a$ and $b$ are positive constants,
$ax^n = \Theta(bx^n)$,
$\log(x^a) = \Theta(\log(x^b))$,
$\log^a(x) = o(x^b)$,
so
$\log^a(x) \ne \Theta(x^b)$
.
If you understand these,
the listed problems should be
straightforward.
