1
$\begingroup$

Function f(x) $n^3 2^n$ is:
a) $O(\ln n)$
b) $O(n^{3 + n})$
c) $O(2^n)$
d) $O (n^3)$
e) None of the above

Definition:

$f(x)$ is $O(g(x))$ as $x \rightarrow \infty$ if there are positive real constants $C$ and $x_0$ such that $f(x) \leq C g(x)$ for all values of $x \geq x_0$.

Choice b) $O(n^{3 + n})$ seems correct, but how is constant C and $x_0$ values chosen. If constant $C$ was large , choice c) $O(2^n)$ could also satisfy $f(x) \leq C g(x)$.

$\endgroup$
  • 2
    $\begingroup$ @avs: you changed the original option b, which was $n^{3+n},$ to $n^3+n$. These are very different and b is no longer correct. $\endgroup$ – Ross Millikan Apr 10 '19 at 21:44
  • $\begingroup$ @RossMillikan edited back. I think now option $b)$ is right $\endgroup$ – vidyarthi Apr 10 '19 at 21:46
  • $\begingroup$ b) is still incorrect: a polynomial is outgrown by an exponential. $\endgroup$ – avs Apr 10 '19 at 21:48
  • 1
    $\begingroup$ Yes, option b is right, but you didn' t get the place in the text that was changed. $\endgroup$ – Ross Millikan Apr 10 '19 at 21:48
  • $\begingroup$ @RossMillikan, you are right, I edited my answer accordingly. $\endgroup$ – avs Apr 10 '19 at 21:52
2
$\begingroup$

No, a polynomial function, $n^k$, is outgrown by the exponential $2^n$. This can be seen by using, say, L'Hopital's rule to compute the limit $$ \lim_{x \rightarrow \infty} {x^k \over 2^x}. $$

The best (i.e., smallest in the order of growth) big-$O$ estimate for $f(n) = n^k 2^n$ is that function itself. All options, except for b) and e), that you are given, grow slower than that, hence can't serve as the upper bound.

However, the function $g(n) = n^n$ does outgrow both exponentials and polynomials, and is present in b). Hence, that's the right option. Yes, it serves as a very crude upper bound, but it is the only upper bound among the options you are given.

For practical guidance, see section "Properties" in this article.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Your definition is not complete. Formally, if $f \sim O(g)$, then $$\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = C \ne 0,$$ where $C < \infty$. Option b) is certainly not correct.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The definition of big O in Wikipedia and elsewhere I have seen it does not impose $\neq 0$. That is reserved for $\Theta$. $\endgroup$ – Ross Millikan Apr 10 '19 at 21:42
  • 1
    $\begingroup$ If the constant $C = 0$, then we might say that $f \sim o(g)$ (little 'o' notation). $\endgroup$ – D.B. Apr 10 '19 at 21:43
  • 1
    $\begingroup$ Yes, that is true, but it is not excluded from big O. We have $n \in O(n^2)$ for example. It is also true that $n \in o(n^2)$ and not true that $n \in \Theta(n^2)$ $\endgroup$ – Ross Millikan Apr 10 '19 at 21:47
  • $\begingroup$ @RossMillikan, perhaps you could explain what is meant by $\Theta$? $\endgroup$ – D.B. Apr 10 '19 at 21:49
  • 1
    $\begingroup$ I believe that is equivalent to your O definition with your $C$ somewhere in $[C_1,C_2]$ $\endgroup$ – Ross Millikan Apr 10 '19 at 21:54
1
$\begingroup$

Option c is not correct. If you claim $n^32^n \in O(2^n)$ I will ask you to state what values $x_0$ and $C$ have. Then I just have to find an $n \gt x_0$ where it fails, which means that $n^3 \gt C$. Clearly I can choose $n$ large enough to do that.

| cite | improve this answer | |
$\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.