0
$\begingroup$

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!

2 Answers 2

1

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

  • 0
    I responded below. Thank you.2019-01-17
1

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

  • 0
    The characterizations of $O$ and $\Theta$ at the beginning of the post are overly restrictive because nothing ensures these limits exist.2019-02-13