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

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?

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