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?
$ \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!
I know that this kind of approximation may not work generally. But this way you can find some bounds on your functions. For example, you can see that the number of steps in \eqref{1} gives a lower bound for number of steps in \eqref{0}, and the sum obtained in \eqref{3} is an upper bound for the sum obtained in \eqref{2}. In this particular case, these bounds together gave a good approximation of the desired function!