-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I don't understand the question. What, for example, would it mean to solve $n^2$ and $n + \log n$? $\endgroup$ Oct 16 '20 at 18:25
  • $\begingroup$ 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. $\endgroup$
    – jelli
    Oct 17 '20 at 8:28
  • $\begingroup$ 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. $\endgroup$ Oct 17 '20 at 8:50
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.