4
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$ – G. Kós Dec 3 '15 at 12:16
  • $\begingroup$ 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? $\endgroup$ – Alex M. Dec 3 '15 at 16:38
  • 3
    $\begingroup$ @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. $\endgroup$ – Mohsen Shahriari Dec 4 '15 at 20:34
  • 1
    $\begingroup$ I would introduce $F(n) = T(n) - \log(n)$ then a direct calculation shows that $F(n) = F\left(\frac{n}{\log(n)}\right)$. $\endgroup$ – Winther Dec 5 '15 at 19:47
  • 1
    $\begingroup$ @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$. $\endgroup$ – George Lowther Dec 8 '15 at 23:35
4
+50
$\begingroup$

$ \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!

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