Big-$O$ notation and constant values

208 Views Asked by At

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

3

There are 3 best solutions below

8
On

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.

0
On

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.

0
On

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.