Prove $n+n^{c}\log n^{c}+1 \in O(n)$ for some $c<1$

Question

I have been trying to prove for the past two days that a function $T(n)\in O(n) , \forall n\in\mathbb{N}$, where $T(n)$ is defined as such:

Let $c<1$,

$T(n)=\begin{cases} n+n^{c}\log n^{c} & c\neq0\\ n & c=0 \end{cases}$

I tried splitting this into three cases - one case for $c=0$, and one case for $c<0$, both of which I've succeeded in proving rather simply. However, I can't find a way to formally prove it for $0<c<1$.

Cheating slightly with Desmos, it appears that for $\boxed{n_0=1},\boxed{c_0=1000}$ we have that $\forall x>n_0,T(n)\leq c_0\cdot n$. I attempted to prove this by induction by showing that $n^{c}\log n^{c} \in O(n)$, but was unable to find a way prove this (or for any constant $c_0$ I could think of, for that matter). I also attempted assuming towards contradiction that it is greater than $c_0\cdot n$

Alternatively, I've seen a proof for this which shows that $\forall c<1$ we have that $\underset{n\rightarrow\infty}{\lim}\frac{n^{c}\log n}{n}=0$ and claims that as this occurs, we have that $T(n) \in O(n)$ however I don't understand the reasoning behind this.

Is there a way to solve this inductively for $0<c<1$? Also, why can we conclude from $\underset{n\rightarrow\infty}{\lim}\frac{n^{c}\log n}{n}=0$ that $T(n) \in O(n)$?

Answer 1

First of all, we will prove by induction that

$n+1\leqslant e^n\quad$ for any $\;n\in\Bbb N\cup\{0\}\,.\quad\color{blue}{(1)}$

For $\;n=0\;$ it results that $\;n+1=1\leqslant e^0=e^n\,.$

Now, we assume that for $\,n=k\in\Bbb N\cup\{0\}\,$ the inequality $\,(1)\,$ holds (induction hyypothesis) and prove that $\,(1)\,$ holds for $\,n=k+1\,$ too.

$n+1=k+2\leqslant 2(k+1)\leqslant2e^k<e\cdot e^k=e^{k+1}=e^n\,.$

Consequently, for induction, it results that $\,(1)\,$ is true for any $\,n\in\Bbb N\cup\{0\}\,.$

---

Secondly, we will prove that

$\ln x<x\quad$ for any $\,x\in(0,+\infty)\,.\quad\color{blue}{(2)}$

If $\;0<x<1\;,\;$ then $\;\ln x<0<x\,.$

If $\;x\geqslant1\;,\;$ then there exists $\;n=\lfloor\ln x\rfloor\in\Bbb N\cup\{0\}\;$ such that

$\ln x<n+1\underset{\overbrace{\text{ by using }(1)\;}}{\leqslant}e^n\leqslant e^{\ln x}=x\,.$

So, in any case, we have proved the inequality $\,(2)\,.$

---

Let $\;0<c<1\,.$

For any $\;n\in\Bbb N\;,\;$ it results that

$(1-c)n^c\ln n^c=c\,n^c\ln\left(n^{1-c}\right)\underset{\overbrace{\text{ by using }(2)\;\\\text{ for }\,x=n^{1-c}>0}\;}{<}c\,n^c\!\cdot\!n^{1-c}=c\,n\;\;,$

$n^c\ln n^c<\dfrac c{1-c}\,n\;\;,$

$n+n^c\ln n^c<n+\dfrac c{1-c}\,n\;\;,$

$n+n^c\ln n^c<\dfrac1{1-c}\,n\;.$

Consequently, there exists $\,M=\dfrac1{1-c}>0\,$ such that

$T(n)<M\!\cdot\!n\quad$ for any $\;n\in\Bbb N\;,$

hence, $\;T(n)\in O(n)\,.$

Answer 2

I have an answer as to why $\underset{n\rightarrow\infty}{\lim}\frac{n^{c}\log n}{n}=0\rightarrow T(n)\in O(n)$. Sharing in case it helps others (note: the limit can be calculated rather easily using L'hopitals rule)

As $\underset{n\rightarrow\infty}{\lim}\frac{n^{c}\log n^{c}}{n}=0$, $\exists n_{0}>0$ s.t $\forall n>n_{0}$ we have that:

$|\frac{n^{c}\log n^{c}}{n}-0|<\boxed{1}$

And as $n>0$, we have that $\frac{n^{c}\log n^{c}}{n}<1$

Thus $n^{c}\log n^{c}\leq\boxed{1}\cdot n$, $\forall n>\boxed{n_{0}}$

Therefore $n^{c}\log n^{c}\in O(n)$ by def.

Therefore $n+n^{c}\log n^{c}\in O(n)$

Answer 3

The standard answer to this is that $\ln(x)=O(x^c)$ for any $c > 0$.

Note that this implies that $\ln(x)=o(x^c)$ for any $c > 0$.

My favorite proof of this starts with, for any $a > 0$,

$\begin{array}\\ \ln(1+x) &=\int_0^x \dfrac{dt}{1+t}\\ &<\int_0^x \dfrac{dt}{(1+t)^{1-a}}\\ &=\int_0^x dt(1+t)^{a-1}\\ &=\dfrac{(1+t)^a}{a}|_0^x\\ &=\dfrac{(1+x)^a-1}{a}\\ &<\dfrac{(1+x)^a}{a}\\ \end{array} $

Choosing $a=c/2$, $\ln(1+x)<\dfrac{(1+x)^{c/2}}{c/2} $ so $\dfrac{\ln(1+x)}{(1+x)^c}<\dfrac{(1+x)^{-c/2}}{c/2} \to 0$ as $x \to \infty$.