Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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)\}$$
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}$.
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})}$$
