Proving function complexity

53 Views Asked by At

I am trying to prove the following: Let $$f(n)=\sum_{i=2}^{n}\frac{1}{i \log i} $$ Where log denotes the natural logarithm. Show that: $$ f(n)=\Theta (\log \log n)$$

I am not sure how to go about showing this. Any help is appreciated. Thanks

1

There are 1 best solutions below

0
On BEST ANSWER

Hint Since $f(x)=x\log x$ is increasing over $[1,\infty)$ so $$\int_2^\infty \frac{dx}{f(x)}\le \sum_{k=2}^\infty\frac{1}{f(k)}\le \frac{1}{f(2)}+\int_3^\infty \frac{dx}{f(x-1)}$$