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

share|improve this question
    
You may be confusing $\Theta(g)$ with $\Omega(g)$, or perhaps simpler with smaller –  Henry Jun 24 '11 at 20:46
add comment

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

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.