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'm trying to prove (by definition) the following but to no avail:

  • $n^{n/2} \ne O(3^{n/2}) $

  • $n! \ne O(3^n)$

  • $(n-b)^a = \Theta(n^a)$

$a,b $ are both constants whereas $a > 0 $ and $b$ might be positive, negative or $0$.

Now , here is what I come up so far:

Lets take the first one for example (regarding the others two I'm completly lost):

Now If we asssume by contradiction that $n^{n/2} = O(3^{n/2}) $ then there exists constants $c,n_0>0$ such that $n^{n/2} < c(3^{n/2}) $ for every $n\ge n_0$.

And if ones look at the ratio:

$n^{n/2} / 3^{n/2} $ then it can be proved that its going to infinity what implies that $n^{n/2} $ is much faster than $3^{n/2} $.

But I have no idea how to show this.

regarding the other ones , can you please give me an hint?

Thanks alot!

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

Problem 1: The solution by Karolis Juodelė is very efficient. Note for example that if $n \ge 12$, then $$\frac{n^{n/2}}{3^{n/2}}\ge \frac{12^{n/2}}{3^{n/2}}=4^{n/2}=2^n.$$ It is standard that $2^n\to\infty$ as $n\to\infty$.

For a less efficient solution, take the log of both sides, using any base $\gt 1$ that you like, such as $2$, or $e$, or $10$.

Problem 2: We want to show that $\dfrac{n!}{3^n}$ blows up, or equivalently that $\dfrac{3^n}{n!}$ approaches $0$. One way to do this is to observe that for $n \ge 6$, we have $$n!=(5!)(6)(7)(8)\dots(n)\ge (5!)(6)(6)\cdots(6)=(5!)(6^{n-5}).$$ But $3^n=(3^5)(3^{n-5})$. It follows that if $n\ge 6$ then $$\frac{3^n}{n!}\le \frac{3^5}{5!}\frac{3^{n-5}}{6^{n-5}}=\frac{3^5}{5!}\frac{1}{2^{n-5}}.$$ This inequality is plenty strong enough to deal with the problem. Note that a similar trick works if $3$ is replaced by, say, $100$.

Problem 3: We are interested in the ratios $$\frac{n^a}{(n-b)^a} \qquad \text{and}\qquad \frac{(n-b)^a}{n^a}$$ for large $n$. For either ratio, divide top and bottom by $n^a$. We get $$\frac{1}{\left(1-\frac{b}{n}\right)^a}\qquad \text{and}\qquad \left(1-\frac{b}{n}\right)^a$$ respectively. Both expressions have limit $1$ as $n\to\infty$.

share|improve this answer
    
I responded below. Thank you. –  SyndicatorBBB Nov 5 '12 at 9:00
add comment

$f = O(g)$ iff $\lim \frac {f}{g} < \infty$. $f = \Theta(g)$ iff $f = O(g)$ and $g = O(f)$ which is the same as $0 < \lim \frac{f}{g} < \infty$.

  1. $\lim \frac{n^{n/2}}{3^{n/2}} = \lim (\frac{n}{3})^{n/2}$. When does $\alpha^n$ go to infinity?

  2. Notice that $n! > \frac {n^n}{e^n}$. Apply that and continue as before.

  3. Not sure how to hint this. The fraction is bounded and decreasing.

share|improve this answer
    
but n/3 isn't an alpha. it depends on n. so its n^n... –  SyndicatorBBB Nov 4 '12 at 15:49
    
Yes, my point was that, say $\lim 2^{n/2} = \infty$ and $\frac{n}{3} > 2$ for all large $n$. –  Karolis Juodelė Nov 4 '12 at 15:52
    
Okay I will try to work with these hints. Thank you. –  SyndicatorBBB Nov 4 '12 at 15:53
    
The characterizations of $O$ and $\Theta$ at the beginning of the post are overly restrictive because nothing ensures these limits exist. –  Did Nov 5 '12 at 9:40
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.