1
$\begingroup$

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I understand the concept and reason behind Big-O, and what it means when one function is Big-O of the other. The problem I am having right now is when I am asked to PROVE that $f(x) = O(g(x))$. I know the basic order of which kinds of functions are a lower order than others, but its questions that have functions with a lot of combinations of different functions that stump me. I don't know where to start analyzing, and from hearing classmates and professors talk it definitely seems like there's some general rule-of-thumb/algorithm that helps with pretty much every Big-O problem.

Can y'all share some insight into how you go about thinking through these problems?

Give a big-O estimate for this function. For the function $g$ in your estimate $f(x)$ is $O(g(x))$, use a simple function $g$ of smallest order.

$(n^3 + n^2\log n)(\log n + 1) + (17\log n + 19)(n^3 +2)$

Or this one: Find the least integer $n$ such that $f(x)$ is $O(x^n)$ for each of these functions.

a) $f(x) = 2x^3 + x^2\log x$

b) $f(x) = (x^3 + 5\log x)/(x^4 + 1)$

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Give a big-O estimate for this function. For the function $g$ in your estimate $f(x)$ is $O(g(x))$, use a simple function $g$ of smallest order. $$x_n=(n^3 + n^2\log n)(\log n + 1) + (17\log n + 19)(n^3 +2)$$

To solve this, one first spots the dominant term in each part, here $n^2\log n\ll n^3$, $1\ll\log n$ and $1\ll n^3$ hence one is left with $$(n^3)(\log n) + (\log n)(n^3),$$ thus, one can guess that $x_n$ is of order $n^3\log n$. Second one proves that $n^3\log n$ is indeed the smallest order big-O. First this is a big-O: indeed for every $n\geqslant3$, $1\leqslant\log n\leqslant n$ and $1\leqslant n^3$ hence $$x_n\leqslant(n^3 + n^2\cdot n)(\log n + \log n) + (17\log n + 19\log n)(n^3 +2\cdot n^3)=112\cdot n^3\log n.$$ Finally, one proves this is the best big-O: indeed $$x_n\geqslant(n^3 + 0)(\log n + 0) +0=n^3\log n.$$

$\endgroup$
3
  • $\begingroup$ Given the premises for the dominant terms in each part, I can follow this, so thanks! But I don't understand where you got $1 \ll n^3$ $\endgroup$ Commented Sep 16, 2014 at 2:57
  • $\begingroup$ It seems intuitive to me that you would have four terms because that's what you started out with. But I don't follow the transition from "$n^2logn \ll n^3, 1 \ll logn, and 1 \ll n^3$" to $(n^3)(logn) + (logn)(n^3)$. $\endgroup$ Commented Sep 16, 2014 at 2:58
  • $\begingroup$ If $a_n\gg b_n$ then $a_n+b_n\sim a_n$. Apply this to each of the four factors. (About $1\ll n^3$, are you serious?) $\endgroup$
    – Did
    Commented Sep 16, 2014 at 8:05

You must log in to answer this question.

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