# Asymptotics of a logarithmic series

Given that,

$$T(n) = \sum_{i=2}^{n} \log_i n$$

I need to find the asymptotic boundary of $$T(n)$$.

Answer given is $$\theta(n)$$. Please provide explanation.

First, the change-of-base formula may be helpful here: $$\log_b(x) = \frac{\ln x}{\ln b}$$ Also, with sums I always find it helps to write out the sum explicitly, so let's do that: $$T(n) = \sum_{i=2}^{n} \log_i n = \log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_n(n)$$

Now if you want to show this is $$\theta(n)$$, there are two things: you should show it is lower bounded by $$cn$$, and it is upper bounded by $$Cn$$, for some constants $$c$$ and $$C$$.

• For the lower bound, use the fact that each term is greater than or equal to $$1$$.

• For the upper bound, I suggest dividing the sum into two parts: from $$i = 2$$ to $$i = \sqrt{n}$$, and $$i = \sqrt{n}$$ to $$n$$. So the first part is $$\left(\log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_{\lfloor\sqrt{n}\rfloor}(n)\right).$$ Here we have $$\sqrt{n}$$ terms, each which is at most $$\log_2(n)$$. The second part is $$\left( \log_{\lceil \sqrt{n} \rceil}(n) + \cdots + \log_n(n) \right).$$ Here we have at most $$n$$ terms, but you can show (using the change of base formula above) that each term is at most $$2$$.

Now adding up the two parts, you should get an upper bound of $$\sqrt{n} \log_2(n) + 2n,$$ so the final step is to show this is $$O(n)$$.

First off, $$\log_i n = \ln n / \ln i$$, so your sum is:

$$\begin{equation*} \sum_{2 \le i \le n} \dfrac{\ln n}{\ln i} = \ln n \sum_{2 \le i \le n} \dfrac{1}{\ln i} \end{equation*}$$

The last sum has no simple form. We can approximate it as an integral:

$$\begin{equation*} \sum_{2 \le i \le n} \frac{1}{\ln i} \approx \int_2^n \frac{d t}{\ln t} \end{equation*}$$

This is known as the Eulerian logarithmic integral $$\operatorname{Li}(n)$$ (see here), it can be shown that $$\operatorname{Li}(n) \sim n / \ln n$$ if $$n \to \infty$$. Thus you get:

$$\begin{equation*} \sum_{2 \le i \le n} \dfrac{\ln n}{\ln i} \sim n \end{equation*}$$

Would need a bit of polish (use integrals to bound the sum from below/above, and use bounds on $$\operatorname{Li}(n)$$) to make if airtight.

(Here we write $$f(n) \sim g(n)$$ if $$\lim_{n \to \infty} f(n) / g(n) = 1$$)