Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples.

The question equation: $f(n) = 6n^3 + n^2\log n$

The exact line written for the answer is: $f(n) \leq 6n^3 + n^2 \centerdot n \text{, for all }n \geq 1, \text{since} \log n \leq n$

First of all, I don't really see why the logarithm was removed or why it actually matters when the dominant piece is the $6n^3$. I also don't get why it's $n \geq 1$ instead of $n \geq 6$ (unless it's a continuation of the first one.

Been staring at it for about 15 minutes and still not getting how it comes down to $n \geq 1$. Would anybody be kind enough to give me a hint as to what's wrong?

-
What's wrong is that you started studying only two days before the midterm. –  Andrej Bauer Nov 21 '12 at 19:38
I started studying about 3 days before this. It's just that I never looked at the examples until now >>. –  Mizuho Nov 21 '12 at 19:55
Ah well, five days instead of two, that completely changes the whole story. –  Andrej Bauer Nov 21 '12 at 20:05
Well, there is the question what it means for you to "study". Anything you are able to learn in just 5 days before the midterm will evaporate. Also, it is very easy to "study" every day and learn almost nothing. –  Andrej Bauer Nov 22 '12 at 1:21
@AndrejBauer: I am sorry, but your comments are off-topic. The question stands at it is, and we should not judge the OPs motivation to ask this question. –  A.Schulz Nov 22 '12 at 8:17

First of all, it is not a "question equation" but the definition of $f$.

The task at hand is to show that $f(n) \in O(n^3)$. By the definition of $O(n^3)$ this means that we need to find $n_0$ and $C$ such that $f(n) \leq C n^3$ for all $n \geq n_0$. There may be many $n_0$ and $C$ that work, we just need to find one.

I pull out of my hat $n_0$ and $C$ that work (because I am a professional mathematician), namely $n_0 = 1$ and $C = 7$. Now we have to verify: for all $n \geq 1$ we have $f(n) \leq 7 n^3$.

Because $\log n \leq n$ whenever $n \geq 1$ (draw a graph of $y = \log x$ and $y = x$, and stare at it for a while) we may replace $\log n$ in the definition of $f$ with $n$, and we will get something bigger. So we have for all $n \geq 1$: $$f(n) = 6 n^3 + n^2 \log n \leq 6 n^3 + n^2 \cdot n = 6 n^3 + n^3 = 7 n^3$$ We have established that $f(n) \leq 7 n^3$ for all $n \geq 1$, as required. We get an A on the midterm.

The question remains how I pulled out of my hat $n_0 = 1$ and $C = 7$, since this is what you will have to do on your mid-term. You start with $f(n)$ and "massage" it into something that is larger and has the form $C n^3$. On the way you observe that your massaging only works for $n$ large enough, and that gives you $n_0$.

Let us have another example: show that $g(n) = 23 n^2 + 17 + \log n$ is in $O(n^2)$. The massaging process goes as follows: turn every term which grows more slowly than $n^2$ into something of the form $C n^2$, and think about which $C$ to use and for which $n$ it is going to work. We have three terms to worry about, and notice how each has several possible ways of massaging:

• the term $23 n^2$ is already in the correct form.
• the term $17$, we give three possibilities just for fun:
• $17 \leq 17 n^2$ for $n \geq 1$
• $17 \leq 17 n^2$ for $n \geq 100$
• $17 \leq n^2$ for $n \geq 5$
• the term $\log n$:
• $\log n \leq 42 n^2$ for all $n \geq 3$

I have purposely chosen weird and suboptmal values for $C$ and $n_0$ for each of the terms to show you that there is a lot of choice. For example, it would have been more "optimal" to say that $\log n \leq n^2$ for $n \geq 1$. For the term $17$ I gave three possible massages, let us work with the second one. We compose our observations together by replacing each term with its upper bound: $$g(n) = 23n^2 + 17 + \log n \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2.$$ I was too lazy to compute $23 + 17 + 42$ so I just approximated it with something larger, namely $1000$. Thus our $C = 1000$. We still have to figure out $n_0$. As far as the term $23 n^2$ is concerned any $n_0$ is ok. The term 17 wants $n_0 = 100$ and the term $\log n$ wants $n_0 = 3$. So we may take any $n_0$ that is larger than or equal 100 and 3, for example let us take $n_0 = 4127$.

We have now successfull pulled $C$ and $n_0$ from a hat. It is time to write the official solution so that we appear to be very smart, and to confuse students who start studying only two days before the midterm:

The function $g(n) = 23n^2 + 17 + \log n$ is in $O(n^2)$ because for every $n \geq 4127$ we obviously have $g(n) \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2$. We used here the easy observations that $17 \leq 17 n^2$ and $\log n \leq 42 n^2$ for every $n \geq 4127$.

-