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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.