Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2 Answers 2

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.