title: Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)
body: <p>The question comes from <a href="https://mitpress.mit.edu/books/introduction-algorithms">Introduction to Algorithms</a> 3rd Edition, P63, Problem 3-6, where it's introduced as <strong><em>Iterated functions</em></strong>. I rewrite it as follows: </p>
  
  <pre><code>int T(int n){
     for(int count = 0; n &gt; 2 ; ++count)
     {
        n = n/log₂(n); 
     }
     return count;
  }
  </code></pre>
  
  <p>Then give as tight a bound as possible on <code>T(n)</code>.</p>
  
  <p>I can make it <code>O(log n)</code> and <code>Ω(log n / log log n)</code>, but can it be tighter?</p>
  
  <hr>
  
  <p>PS: Using Mathematica, I've learned that when <code>n=1*10^3281039</code>, <code>T(n)=500000</code> </p>
  
  <p>and the same time, <code>T(n)=1.072435*log n/ log log n</code></p>
  
  <p>and the coefficient declines with <code>n</code> from <code>1.22943</code> (<code>n = 2.07126*10^235</code>) to <code>1.072435</code> (<code>n = 1*10^3281039</code>).</p>
  
  <p>May this information be helpful.</p>