# Some Big-O complexity definition proofs

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!

-

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

-
I responded below. Thank you. –  SyndicatorBBB Nov 5 '12 at 9:00

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

-
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