# Giving tight asymptotic bounds for $T ( n ) = T \left( \frac n { \log n } \right) + \log \log n$

I don't like coming here for such matters, but this is a homework problem from my analysis of algorithms class.

I've come along the Akra-Bazzi method and different variations on the matter, read several papers on the uses, purposes and proofs of it and found a particular result that really helped me push through this problem.

Find tight asymptotic bounds for the following recurrence:

$$T ( n ) = T \left( \frac n { \log n } \right) + \log \log n$$

The issue is I seriously doubt my teacher will be happy with me using different methods. So I've tried doing it the way they taught us in class and got nowhere, as:

• recursion tree method fails right off the bat, as it forces me to use the concept of iterated logarithm (not used in class);
• iteration method yields tedious terms; haven't found a way to derive a closed form for the partial sum, really doubt there is one;
• substitution method isn't of much help since I can't actually guess tight bounds;
• change of variable + something else might(?) work out, but I can't figure out a proper transformation.

Can anyone point a way?

• Introduce $t(x)=T(e^x)$. For $x=\log n$ and $y=\log\frac{n}{\log n}$ we have $t(x)-t(y)=x-y$. – G. Kós Dec 3 '15 at 12:16
• I don't get it: a recurrence should have a base case, which in your case is missing. Also, since $\dfrac n {\log n}$ is not a natural number, do I understand correctly that your recursion is over the real numbers? I suspect that $n > 1$, but what happens if $n < \Bbb e$: instead of going backwards, you go upwards (at least for the very first step), so are you sure that this recursion ends for every $n$, without zig-zagging up and down? – Alex M. Dec 3 '15 at 16:38
• @AlexM. In the analysis of algorithms, many variables may appear as approximations. for example $\frac n{\log n}$ may mean $\left\lfloor\frac n{\log n}\right\rfloor$or $\left\lceil\frac n{\left\lfloor\log n\right\rfloor}\right\rceil$ and people may not care about it! That's for example because the number of operations done by a program is not important to be 10 more or 100 less. The important thing is a measure of "how big" the numbers are. So the equation above has no problem, if it's interpreted this way. – Mohsen Shahriari Dec 4 '15 at 20:34
• I would introduce $F(n) = T(n) - \log(n)$ then a direct calculation shows that $F(n) = F\left(\frac{n}{\log(n)}\right)$. – Winther Dec 5 '15 at 19:47
• @Winther: Right, so iterating this you can show that, for any $x>e$ and any $n$ we have $F(n)=F(m)$ for some $m\in(e,x)$. As long as $T$ is bounded on $(e,x)$ this gives $F(n)=O(1)$ and $T(n)=\log n+O(1)$ over $n\ge e$. – George Lowther Dec 8 '15 at 23:35

$$\def \t {\quad \longrightarrow \quad}$$ You can easily check that $$T ( n ) = \log n$$ satisfies the equation.
But how did I find it out? Let's see how many times we should apply the function $$n \mapsto \frac n { \log n }$$ to make $$n$$ become $$O ( 1 )$$. $$n \t \frac n { \log n } \t \frac { \frac n { \log n } } { \log \frac n { \log n } } \t \dots \tag 0 \label 0$$ You can see that $$\log \frac n { \log n } = \log n - \log \log n = \Theta ( \log n )$$. What would happen if we divided $$n$$ by $$\log n$$, and again by $$\log n$$, and so on? $$n \t \frac n { \log n } \t \frac n { ( \log n ) ^ 2 } \t \dots \tag 1 \label 1$$ Now, if $$\frac n { ( \log n ) ^ k } \approx 1$$ then $$n \approx ( \log n ) ^ k$$ and $$\log n \approx k \log \log n$$ and thus $$k \approx \frac { \log n } { \log \log n }$$. So after approximately $$\frac { \log n } { \log \log n }$$ steps we would get $$O ( 1 )$$.
Next let's see what we're summing up in our steps: $$0 \t \log \log n \t \log \log n + \log \log \frac n { \log n } \t \dots \tag 2 \label 2$$ Again, it's easy to see that $$\log \log \frac n { \log n } = \log \log n - \log \log \log n = \Theta ( \log \log n )$$. What would happen if we added $$\log \log n$$ to our sum every step? $$0 \t \log \log n \t 2 \log \log n \t \dots \tag 3 \label 3$$ Now, if we do it for $$k$$ times, the sum will approximately be equal to $$\frac { \log n } { \log \log n } \cdot \log \log n = \log n$$. So $$T ( n ) = \log n$$ may be a good candidate for checking!