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$
5
  • 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$ Apr 10, 2019 at 21:44
  • $\begingroup$ @RossMillikan edited back. I think now option $b)$ is right $\endgroup$
    – vidyarthi
    Apr 10, 2019 at 21:46
  • $\begingroup$ b) is still incorrect: a polynomial is outgrown by an exponential. $\endgroup$
    – avs
    Apr 10, 2019 at 21:48
  • 1
    $\begingroup$ Yes, option b is right, but you didn' t get the place in the text that was changed. $\endgroup$ Apr 10, 2019 at 21:48
  • $\begingroup$ @RossMillikan, you are right, I edited my answer accordingly. $\endgroup$
    – avs
    Apr 10, 2019 at 21:52

3 Answers 3

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.

$\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.

$\endgroup$
8
  • 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$ Apr 10, 2019 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, 2019 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$ Apr 10, 2019 at 21:47
  • $\begingroup$ @RossMillikan, perhaps you could explain what is meant by $\Theta$? $\endgroup$
    – D.B.
    Apr 10, 2019 at 21:49
  • 1
    $\begingroup$ I believe that is equivalent to your O definition with your $C$ somewhere in $[C_1,C_2]$ $\endgroup$ Apr 10, 2019 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .