# How to solve asymptonic notation f(n) = 3^n−n^2 and h(n) = 2^n

Assumef,g,hare three asymptotically nonnegative functions i.e.f(n),g(n),h(n)≥0 for all values of n∈N∪{0}. Furthermore,f(n) =O(g(n)) andg(n) =O(h(n)). Answer following questions as True or False. Justify your answer.

a) f(n) = 3^n−n^2 and h(n) = 2^n

We take limits and then what.I got stuck while doing log.

• I don't understand the question. What, for example, would it mean to solve $n^2$ and $n + \log n$? Oct 16 '20 at 18:25
• Assumef,g,hare three asymptotically nonnegative functions i.e.f(n),g(n),h(n)≥0 forall values of n∈N∪{0}. Furthermore,f(n) =O(g(n)) andg(n) =O(h(n)). Answer following questions asTrue or False. Justify your answer. Oct 17 '20 at 8:28
• I still don't understand the question. In any case, instead of answering in the comments, please update the original question. Also, please include a complete statement of the question in its body – when reading a question, we often skip the title. Oct 17 '20 at 8:50

By definition, for non negative case, we have $$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$
1. If we can understand OP as desire to find which big-$$O$$ belong $$f$$, then it do not need to necessary consider limits: $$f(n)=3^n-n^2=3^n\left(1-\frac{n^2}{3^n} \right)\leqslant C 3^n \in O(3^n)$$. Now we need solve inequality $$1 \geqslant \frac{n^2}{3^n}$$.
2. If we understand OP as desire to find which asymptotical interrelation have $$f$$ and $$h$$, then let's, for example, consider $$h(n) \leqslant C f(n)$$ and try to solve it: $$2^n \leqslant C (3^n-n^2) \Leftrightarrow \frac{1}{1-\frac{n^2}{3^n}} \leqslant C \frac{3^n}{2^n}$$ again we come to need to have solution for $$1 \geqslant \frac{n^2}{3^n}$$.
Desired solutions we can obtain having: $$\frac{n^2}{3^n}=\frac{n^2}{(1+2)^n}=\frac{n^2}{1+2n+\frac{n(n-1)}{2}2^2+\frac{n(n-1)(n-2)}{3!}2^3+\cdots +2^n}<\\ < \frac{n^2}{\frac{n(n-1)(n-2)}{3!}2^3}=\frac{1}{n}\frac{3}{4(1-\frac{1}{n})(2-\frac{1}{n})}$$