Prove function is in $\mathcal{O}(x\log(x))$

52 Views Asked by At

Consider $T, g: \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ which are bounded on any bounded interval, satisfy $$T(x)=2 T(x / 2)+g(x)$$ for every real number $x \geqslant 1$ and $g(x)=\mathcal{O}(x)$.

I would like to show $T(x)=\mathcal{O}(x \log (x))$. For this I want to show $\lim_{x\rightarrow \infty} \dfrac{T(x)}{x\log(x)}$ is finite.

Notice $$T(x)=2^nT(x/2^n)+2^{n-1}g(x/2^{n-1})+\ldots+2g(x/2)+g(x)\leq2^nT(x/2^n)+nCx$$ where $C$ is a constant such that $g(x)\leq Cx$.

Then $$\lim\limits_{x\rightarrow \infty} \dfrac{T(x)}{x\log(x)}\leq \lim\limits_{x\rightarrow \infty} \dfrac{2^nT(x/2^n)+nCx}{x\log(x)}=\lim\limits_{x\rightarrow \infty} \dfrac{2^nT(x/2^n)}{x\log(x)}.$$

Now I tried taking $n\rightarrow \infty$ and setting $x=2^n$ to simplify all terms but I am really not sure I am allowed to do this.

Do you have any idea how to finish the proof?

1

There are 1 best solutions below

0
On BEST ANSWER

You don't need to prove that the limit is finite the limit can even not exist. However, you can easily prove that the function is bounded. Indeed, for $x\in \mathbb R_{>0}$, $n = \left\lceil\log_2(x)\right\rceil$ then $$\log_2(x) \le n \le \log_2(x) + 1 \implies x \le 2^n \le 2x \implies \frac12 \le \frac{x}{2^n} \le 1$$ and

\begin{align} \frac{T(x)}{x\log_2(x)} &\le \frac{T\left(\frac x{2^n}\right)}{\frac x{2^n} \log_2 x} + C\frac{n}{\log_2x}\\ &= \frac{\sup_{t\in\left[\frac12,1\right]} T(t)}{2 \log_2(x)} + C\left(1 + \frac1{\log_2(x)}\right) \end{align}

Can you finish the proof?