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?

  • 3
    $\begingroup$ What's wrong is that you started studying only two days before the midterm. $\endgroup$ – Andrej Bauer Nov 21 '12 at 19:38
  • $\begingroup$ I started studying about 3 days before this. It's just that I never looked at the examples until now >>. $\endgroup$ – Mizuho Nov 21 '12 at 19:55
  • 2
    $\begingroup$ Ah well, five days instead of two, that completely changes the whole story. $\endgroup$ – Andrej Bauer Nov 21 '12 at 20:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 22 '12 at 1:21
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.

| cite | improve this answer | |

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.