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

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.