2
$\begingroup$

I am a total beginner with the big theta notation. I need find a way to show that $f \in \Theta(g)$, where $f(n) = n$, $g(n) = n + 1/n$, and that $f, g : Z^+ \rightarrow R$. What confuses me with this problem is that I thought that "$g$" is always supposed to be "simpler" than "$f$." But I think I missed something here.

  • 0
    You may be confusing $\Theta(g)$ with $\Omega(g)$, or perhaps *simpler* with *smaller*2011-06-24

2 Answers 2

4

As always first cross-check at wikipedia what you need to show. In this case you want to find $k_1,k_2 > 0$ such that $|g(n)|\cdot k_1 \leq |f(n)| \leq |g(n)|\cdot k_2$ for all $n>n_0$ where $n_0 \in \mathbb{N}$ to show that $f \in \Theta(g)$.

As you work with positive numbers you have

$(n+1/n)\cdot k_1 \leq n \leq (n+1/n)\cdot k_2$

Obviously the right inequality is easy as you can choose $k_2=1$.

For the second you have that

$(n+1/n) \leq (n+1) \leq 2n$ and therefore you can choose $k_1=\frac{1}{2}$. Done with $n_0 = 1$.

2

You are sort of right about thinking that "$g$" is supposed to be simpler than "$f$", but not technically right. The formal definition says nothing about simpler.

However, in practice one is essentially always comparing something somewhat messy, on the left, with something whose behaviour is sort of clear(er) to the eye, on the right.

For the actual verifications in this exercise, it would have made no difference if the functions had been interchanged, so probably the "colloquially standard" version should have been used. But maybe not, once or twice. Now you know a little more about the symmetry of the notion.