Csdrhrt

Task

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

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

$f(x)=ncdot log(n^2+1)+n^2cdot 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}(xcdot log(x))$. Because $3x^2$ is $mathcal{O}(x^2)$, Theorem 2 tells us that $f(x)$ is $mathcal{O}(max(xcdot log(x), x^2))$. Because $xcdot 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_1cdot 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 $ncdot log(n^2+1)$ is $mathcal{O}(n^2cdot 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 $nlog(n^2 + 1)$ is $mathcal{O}(n^2log(n))$, from Theorem 2 $nlog(n^2 + 1) + n^2log(n)$ is $mathcal{O}(max{n^2log(n), : n^2log(n)}) = mathcal{O}(n^2log(n))$.

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

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