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

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