# 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))$
-
Hint: start by picking two of them and trying to tell if they are equivalent. – Colin McQuillan Feb 1 '13 at 10:41

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$.

-

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.

-