Does $i(n) < \log (n)$ imply $\frac{\log i(n)}{n} \in o \left( \frac{\log n}{n} \right)$?

30 Views Asked by At

$i(n)$ is a sequence of nonnegative numbers (integers) indexed by $n$. I think it only implies $ ... \in O\left(\frac{\log n}{n} \right)$, yet the other assertion was made in some paper I am reading. Just wanted to confirm.

Here's the relevant section from the paper

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

One way to check that $f(n)\in o(g(n))$ is to see if $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$.

In this case, $$ \lim_{n\to\infty}\frac{[\log i(n)]/n}{[\log n]/n} = \lim_{n\to\infty}\frac{\log i(n)}{\log n} \leq \lim_{n\to\infty}\frac{\log\log n}{\log n} = 0 $$ using monotonicity of the logarithm, so $\frac{\log i(n)}n\in o\left(\frac{\log n}n\right)$.