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?
$\endgroup$ 02 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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). $$
$\endgroup$
