Search code examples
algorithmsubstitutionrecurrenceproofinduction

Recurrence with logs T(n) = T(logn)+log(log(n))

How to find T(n)=Θ(f(n)) for the recurrence T(n) = T(logn)+log(log(n))?

I think T(n)= Θ(log(n)) but the proof is the hard part for me. I'm going to attempt to prove by substitution but please help me with that. I also tried a proof by induction but that got out of hand quickly...

Assume T(n) = logn such that

proof of big o:

T(n+1) = T(log(n+1))+loglog(n+1)
       = loglog(n+1) + loglog(n+1) < c*log(n) (check)

proof of big ohmega:

T(n-1) = T(log(n-1))+loglog(n-1)
       = loglog(n-1) + loglog(n-1) > c*log(n) (not good)

Thoughts on proving this via sub. or via induction? ... wish I could just plug and chug into master theorem ~

Solution

  • Direct approach seems the best fit.

    T (n) = log log n + T (log n) =
        log log n + log log log n + T (log log n) =
        log log n + log log log n + log log log log n + T (log log log n) =
        log log n + log log log n + log log log log n + log log log log log n + ...

    The first term is log log n, and every term dominates the next one.
    So the function is Omega (log log n).