# Give a big-O estimate for a function f(x), use a simple function g of the smallest order.

Task

Find a function $g(x)$ that is Big-O of $f(x)$

$f(x)$ is $\mathcal{O}(g(x))$

$f(x)=n\cdot log(n^2+1)+n^2\cdot log(n)$

I tried to follow/copy one of the examples in my book Discrete Mathematics and Its Applications. Rosen, 7e

Example from book

Give a big-O estimate for $f(x) = (x+1) log(x^2 + 1) + 3x^2$.

Solution:

First, a big-O estimate for $(x + 1) log(x^2 + 1)$ will be found. Note that $(x + 1)$ is $\mathcal{O}(x)$. Furthermore, $x^2 + 1 ≤ 2x^2$ when $x > 1$. Hence,

$log(x^2+1) ≤ log(2x^2)=log(2)+log(x^2)=log(2)+2log(x)≤3log(x)$

if $x > 2$. This shows that $log(x^2 + 1)$ is $\mathcal{O}(log(x))$.

From Theorem 3 it follows that $(x + 1) log(x^2 + 1)$ is $\mathcal{O}(x\cdot log(x))$. Because $3x^2$ is $\mathcal{O}(x^2)$, Theorem 2 tells us that $f(x)$ is $\mathcal{O}(max(x\cdot log(x), x^2))$. Because $x\cdot log(x) ≤ x^2$, for $x > 1$, it follows that $f(x)$ is $\mathcal{O}(x^2)$.

Theorem 2

Suppose that $f_1(x)$ is $\mathcal{O}(g_1(x))$ and that $f_2(x)$ is $\mathcal{O}(g_2(x))$. Then $(f_1 + f_2)(x)$ is $\mathcal{O}(max(|g1(x)|, |g2(x)|))$

Theorem 3

Suppose that $f_1(x)$ is $\mathcal{O}(g_1(x))$ and that $f_2(x)$ is $\mathcal{O}(g_2(x))$. Then $(f_1\cdot f_2)(x)$ is $\mathcal{O}(g_1(x)\cdot g_2(x))$.

I did not managed to find the answer, nor do I know if what I did, I did correctly, but could anyone explain to me how to properly solve the task? This was what I managed to produce:

$log(n^2+1) ≤ log(2n^2) = log(2) + log(n^2) = log(2) + 2log(n) ≤ 3log(n)$

if $n>2$ then $log(n^2+1)$ is $\mathcal{O}(log(n))$

if $n>1$ then $n$ is $\mathcal{O}(n^2)$

Theorem 3 shows us that $n\cdot log(n^2+1)$ is $\mathcal{O}(n^2\cdot log(n))$

What am I supposed to do now?

## 2 Answers

First of all, why did you specify that $\log(n^2 + 1)$ is $\mathcal{O}(\log(n))$ "if $n \ge 2$"? Big O notation describes the asymptotic behaviour of a function, so it is independent on the specific values assumed by the variable(s).

That said, not only what you did is correct, but you are practically finished. Indeed, since $n\log(n^2 + 1)$ is $\mathcal{O}(n^2\log(n))$, from Theorem 2 $n\log(n^2 + 1) + n^2\log(n)$ is $\mathcal{O}(\max\{n^2\log(n), \: n^2\log(n)\}) = \mathcal{O}(n^2\log(n))$.

Note that you could've improved your bound on $n\log(n^2 + 1)$, since actually it is also $\mathcal{O}(n\log(n))$. However it doesn't matter in the end since the second summand ($n^2\log(n)$) is the dominant one.

I would do it much simpler: you can easily check that $$n\log(n^2+1) = o(n^2\log n), \quad\text{so} \quad n\log(n^2+1)+n^2\log n\sim_\infty n^2\log n,$$ which implies $$n \log(n^2+1) + n^2\log n =\mathcal{O}( n^2\log n).$$