# Big-$O$ notation and constant values

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

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

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.

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.

• The definition of big O in Wikipedia and elsewhere I have seen it does not impose $\neq 0$. That is reserved for $\Theta$. – Ross Millikan Apr 10 '19 at 21:42
• If the constant $C = 0$, then we might say that $f \sim o(g)$ (little 'o' notation). – D.B. Apr 10 '19 at 21:43
• 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)$ – Ross Millikan Apr 10 '19 at 21:47
• @RossMillikan, perhaps you could explain what is meant by $\Theta$? – D.B. Apr 10 '19 at 21:49
• I believe that is equivalent to your O definition with your $C$ somewhere in $[C_1,C_2]$ – Ross Millikan Apr 10 '19 at 21:54

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.