1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.