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$
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$
  • $\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$ – UnworthyToast Sep 16 '14 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$ – UnworthyToast Sep 16 '14 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 Sep 16 '14 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.