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})}$$