1
$\begingroup$

I've been doing a series of problems regarding big-O notation, and I was under the impression that I had a grasp on it until I found this one: 'Is the statement $(\log n)^2+{1\over 30}\log n \in O((\log n)^2)$ true or false?'

I did the following steps in an attempt to compute this: $$ \begin{align} (\log n)^2+{\log n\over 30} &\leq |\log n|^2 + {1\over 30}|\log n|\\ &\leq |\log n|^2 + {1\over 30}|\log n|^2\\ &= {31\over 30}|\log n|^2 \end{align} $$ However, in testing with Desmos, I found that this was false, and that the original statement is in turn false. What am I missing, in regards to my process? I clearly have some misconception but I can't necesserily spot it.

$\endgroup$

1 Answer 1

2
$\begingroup$

The only error you made is where you have written $$ |\log n| \le |\log n|^2 \tag{1} $$ in your second line. This is not true for all $\pmb n$, since for some small values of $n$, $|\log n| > |\log n|^2$. However, big-O notation is about capturing the behavior of the functions for large values of $\pmb n$ (or whatever the parameter is, more generally). So while $(1)$ is not true for every $n$, it is sufficient for big-O that it be true for all $n$ sufficiently large, say for $n > 10$.

In conclusion, if you write "assume $n> 10$" right at the top of your proof, then your entire proof is correct, and you can conclude the given statement is true.

$\endgroup$

You must log in to answer this question.

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