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