0
$\begingroup$

I was out all last week sick with the flu and am trying to get caught up in my Discrete Mathematics course. One set of questions in my book goes as follows:

Find the least integer $n$ such that $f(x) \in O(x^n)$ for each of the functions:

(a). $f(x) = 8x+4$
(b). $f(x) = x\sqrt(x)$
(c). $f(x) = log_3 9$
(d). $f(n) = n!$

Can someone walk me through this? I have no idea where to even begin on these or what it is I am attempting to do in the end.

$\endgroup$

2 Answers 2

1
$\begingroup$

The general concept of "Big-O" is that function $f$ is in Big-O of function $g$ if $f(x)$ grows no faster than $g(x)$ as $x\to\infty$. Generally speaking both $f$ and $g$ take positive values, so more precise ways of saying this are:

  • $f\in O(g)$ if there is a constant $C>0$ such that $f(x)\le Cg(x)$ for all large $x$

  • $f\in O(g)$ if the ratio $f(x)/g(x)$ remains bounded as $x\to\infty$.

The function $g$ is therefore an upper bound on the asymptotic growth rate of $f$. Since $g$ is only an upper bound, there are many choices for $g$.

The point of a big-O analysis is to make a statement about the growth rate of a function, which in turn allows you to compare growth rates ("complexity") of different functions. In analysis of algorithms, you generally prefer algorithms that don't grow too fast with the size of the problem. For example if you want to sort a list of $n$ items, a naive 'selection' algorithm might build the sorted list by selecting the smallest item from the list, then the next smallest, and so on; this algorithm has complexity $O(n^2)$. The fastest sort algorithms have a complexity that is $O(n\log n)$, which grows considerably slower than the selection algorithm, and therefore can handle much larger problems.

There are related concepts $f\in o(g)$ ("little oh", which gives a lower bound on the growth of $f$) and $f\in\Theta(g)$ ("theta", which gives both upper and lower bounds).

Back to your problem: You have to find the smallest integer $n$ such that $f(x)\le Cx^n$ as $n\to\infty$. Taking the smallest $n$ amounts to finding the sharpest upper bound.

To solve part (a), you have $f(x)=8x+4$ is a linear function, so certainly $f\in O(x)$.

  • Proof (1): $f(x)\le 10x$ for all large $x$.

  • Proof (2): As $x\to\infty$, we see that $f(x)/x\to 8$ so the ratio $f(x)/x$ remains bounded as $x\to\infty$.

It's also true that $f\in O(x^2)$ and that $f\in O(x^{2.3})$, but $n=1$ wins because it's the smallest $n$ such that $f(x)/x^n$ stays bounded as $x\to\infty$.

For the remaining parts, just ask yourself "how does $f(x)$ grow as $x$ gets larger, and can I place a polynomial upper bound on this growth?" (The answer to the second question can be "no".)

$\endgroup$
0
$\begingroup$

grand_chat has already explained the concept of Big-O to you. However, for your exercise, it might be easier to understand if you use the following definition:

$f(x) \in O(g(x))$ if there exists positive constants $C$ and $x_0$ such that:

$\quad\quad 0 \le f(x) \le Cg(x)$ for all $x \gt x_0$

a) $f(x) = 8x + 4 \le 8x + 8x = 16x$ for $x \ge 1$
$\quad$So, $C = 16$, $x_0=1$ and $g(x) = x$
$\quad$So, $f(x)=O(g(x))=O(x^1)$

b) $f(x) = x\sqrt(x) = x^{\frac {3}{2}} \le x^2 $ for $x \gt 0$
$\quad$So, $C = 1$, $x_0=1$ and $g(x) = x$
$\quad$So, $f(x)=O(g(x))=O(x^1)$

c) $f(x)= log_39 = 2 \le 3(x^0)$ for $x \ge 1$
$\quad$So, $C = 3$, $x_0=1$ and $g(x) = x^0$
$\quad$So, $f(x)=O(g(x))=O(x^0)$

d) $f(n) = n! = n(n-1)...1 \le n^n$
$\quad$So, $C = 1, g(n) = n^n$

$\endgroup$

You must log in to answer this question.

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