What is the sum of recursive logarithms?

Question

I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form:

$$ O(n \times (\sqrt n)^2 + n \times (\lg \sqrt n)^2 + n \times (\lg \lg \sqrt n)^2 + \space ... + \space n \times a^2) $$

$$ = O(n^2 + n \times (\lg n)^2 + n \times (\lg \lg n)^2 + \space ... + \space n \times a^2) $$ Where $a$ is a constant value.

I have a hunch that in the limit to infinity $n^2$ dominates. However I do not know how to prove this. Is there a closed form for the sum of recursive logarithms, such as I have in the above formula?

Answer 1

You are right. $n^2$ dominates. It is because $\log(n)$ is asymptotically lower than $n$ and $n$ is asymptotically lower than $n^2$. This is very easy to prove. If your book/class allows you to assume this then just state it and you're done. If this assumption is not allowed(well it should be) you can prove by showing that,

$$\frac{d(\log(x))}{dx}\lt\frac{dx}{dx}\lt \frac{d(x^2)}{dx}$$

for sufficiently large $x$.