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

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^nleft(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})}$$