How does $\log(x^2 + 1)$ become $\log(2x^2)$?

Question

My textbook attempts to take the big O of $\log(x^2 +1)$. It proceeds by saying $x^2 + 1 \le 2x^2$ when $x \ge 1$. But I don't know how it came up with this idea.

Question:

Why set $x^2+1$ to a random value to be $2x^2$? Why $2$ of all numbers? Why not $x^2$ or $x^3$?

Answer 1

We’re not setting $x^2+1$ to anything. We want to find an upper bound on $\log(x^2+1)$ that can be expressed as a fairly simple function of $x$. Provided that $x\ge 1$, we know that $x^2+1\le 2x^2$, so $\log(x^2+1)\le\log(2x^2)$, and $\log(2x^2)$ can be expressed as a simple function of $\log x$:

$$\log(2x^2)=\log 2+2\log x\;.$$

If $x\ge 2$, we know that $\log x\ge\log 2$, and therefore

$$\log(x^2+1)\le\log 2+2\log x\le 3\log x\;.$$

This is exactly the kind of thing that’s needed in order for us to conclude that $\log(x^2+1)$ is $O(\log x)$: we have constants $M$ and $c>0$ such that

$$\log(x^2+1)\le c\log x$$

for all $x\ge M$. Specifically, we can use $M=2$ and $c=3$.

We couldn’t have used $x^2$, because $x^2+1$ isn’t less than or equal to $x^2$. We could have used $x^3$: $x^2+1\le x^3$ for $x\ge 2$, say, so

$$\log(x^2+1)\le\log x^3=3\log x$$

for $x\ge 2$, and again we’ve shown that $\log(x^2+1)$ is $O(\log x)$.

We could have used $5x^2$: $x^2+1\le 5x^2$ for $x\ge 1$, so

$$\log(x^2+1)\le\log(5x^2)=\log 5+2\log x\;.$$

And $\log 5+2\log x\le3\log x$ for $x\ge 5$, so $\log(x^2+1)\le3\log x$ for $x\ge 5$, and again we’ve shown that $\log(x^2+1)$ is in $O(\log x)$.

Answer 2

You could have taken $3 x^2$ if you wanted, or $x^3$. You'd end up with the same result. But not $x^2$: it's certainly not true that $x^2 + 1 \le x^2$.

Answer 3

I can give some observations.

• My guess for changing $x^2+1$ to $2x^2$ is to get rid of the $+1$ and get a monomial (one term) so that taking the log is easier.
• $x^3$ would not be good because it is asymptotically too fast compared to $x^2+1$. Try following the textbook using $x^3$ instead of $2x^2$ and you'll get an upper bound (big-O notation) that is looser (bigger) than the one produced by $2x^2$ and therefore gives less information about the growth of $\log(x^2+1)$. Edit: the big-O notation result will be the same if you use $x^3$, but all the inequalities before applying big-O will be looser. In this example it doesn't matter, but usually you want to bound things more tightly/closely rather than loosely.
• The coefficient $2$ is arbitrary. You could use $1.000000001 x^2$ instead for a slightly tighter bound! Anything $>1$ is ok.