Bounding $\frac{(n^2 +\log_5(n))\cdot \log_8(\log_2(\frac{\sqrt{n}}{2}))}{2}$ from above and below

Question

Can this expression be bounded by a polynomial of degree $2$ from above and below ?

If yes then i have bounded it from below by $n^2$ which is trivial,what i'm having trouble with is bounding it from above.

I'm trying to bound this from above and blow to prove that its $\theta(n^2)$ where theta is the big-theta notation from time complexity of algorithms which bounds a functions from above and below, so it defines exact asymptotic behavior.

Update:

Now that we agree that this is not $\theta(n^2)$I am now investigation if its $\theta(n^{2}\cdot logn)$, by calculating the limit $ \lim_{n \to \infty}{\frac{f(n)=\frac{(n^2 +\log_5(n))\cdot \log_8(\log_2(\frac{\sqrt{n}}{2}))}{2}}{g(n)=n^{2}\cdot logn}}$.

I have found out that it's equal to zero which means $n^{2}\cdot \log n$ grows much faster than the numerator which means that $f(n)=o(g(n))$ but as i know I can't have $f(n)$ to be little-$o$ of $g(n)$ if i'm trying to show that $f(n)=\theta(g(n))$ ,does this mean that this is also not $\theta(n^{2}\cdot \log n)$ or did i go wrong about it?

Answer 1

It is not possible to bound it from above by a polynomial of degree $2$.

If there exists $a,b,c>0$ such that: $$\frac{(n^2 +\log_5(n))\cdot \log_8(\log_2(\frac{\sqrt{n}}{2}))}{2} \leq a n^2+b n+c$$ then dividing by $n^2$ $$\frac{(1 +\frac{\log_5(n)}{n^2})\cdot \log_8(\log_2(\frac{\sqrt{n}}{2}))}{2} \leq a +b \frac{1}{n}+c \frac{1}{n^2}$$ as: $$\lim_{n \to \infty} 1 +\frac{\log_5(n)}{n^2}=1$$ $$\lim_{n \to \infty} \log_8(\log_2(\frac{\sqrt{n}}{2}))=+\infty$$ $$\lim_{n \to \infty} a +b \frac{1}{n}+c \frac{1}{n^2}=a$$ you obtain by taking $n \to \infty$ in the inequalities $+\infty \leq a$ which is a contradiction.

---

Remark: one can show that in fact the correct relut is $\theta(n^2 \log(\log(n))$ and for most practical application $\log(\log(n))$ is almost constant.

---

To expand my comments:

The key idea to compute the asymptotic behavior is to keep only the "largest" term in any sum. And when faced with product use that $\theta(f) \times \theta(g)=\theta(fg)$.

In our case:

• We have a product $(n^2 +\log_5(n))\cdot \log_8(\log_2(\frac{\sqrt{n}}{2}))$ so we must evaluate the asymptotic of each term:
• As $n^2 \gg \ln(n)$ (i.e $\ln(n)=o(n^2)$) we have: $$n^2 +\log_5(n)=n^2+\frac{1}{\ln(5)} \ln(n)=\theta( n^2)$$
• For the other term e can use the properties of $\ln$: \begin{align} \log_8(\log_2(\frac{\sqrt{n}}{2}))&=\frac{1}{\ln(8)} \ln \left(\frac{1}{\ln(2)} \left(\frac{1}{2} \ln(n)-\ln(2) \right) \right)\\ &=\frac{1}{\ln(8)} \left(\ln \left(\frac{1}{\ln(2)}\right)+\ln\left( \left(\frac{1}{2} \ln(n)-\ln(2) \right) \right)\right) \end{align} and: $$\frac{1}{2} \ln(n)-\ln(2)=\frac{\ln(n)}{2} \left(1-\frac{2\ln(2)}{ \ln(n)} \right)=\frac{\ln(n)}{2} \left(1+o(1) \right)$$ so: $$\ln \left(\frac{1}{2} \ln(n)-\ln(2)\right)=\ln \left(\frac{\ln(n)}{2} \left(1+o(1) \right) \right)=\ln(\ln(n))-\ln(2)+\ln(1+o(1))=\ln(\ln(n))+o(\ln(\ln(n))$$ as$\ln(\ln(2))=o(\ln(\ln(n))$ you obtain: $$\log_8(\log_2(\frac{\sqrt{n}}{2}))=\frac{1}{\ln(8)} \left( \ln(\ln(n))+o(\ln(\ln(n)) \right)=\theta(\ln(\ln(n))$$ so multiplying the results you obtain that the initinial function is: $$\theta(n^2 \ln(\ln(n)))$$