<p>The solution is $T(n) = \Theta(\log n /\log\log n)$.  (I'm assuming the $O(1)$ term in the recurrence is really $\Theta(1)$, since otherwise $T(n)$ has no lower bound.)</p>

<p>As you and Tsuyoshi already observed, you can derive a lower bound by overestimating the denominator in the recursive argument.  Consider the function $L_k(n)$ defined by the recurrence
$$
L_k(n) = L_k\left(\frac{n}{\log k}\right) + \Theta(1).
$$
The solution $L_k(n) = \Theta(\log n / \log \log k)$ follows from standard methods.  An easy inductive argument implies that $T(n) \ge L_k(n)$ for any $k\ge n$.  Thus, setting $k=n^2$ (for example) immediately gives us $T(n) = \Omega(\log n/\log\log n)$.</p>

<p>For the upper bound, the symmetric trick is to <em>under</em>-estimate the denominator in the recursive argument.  Consider the function $U_k(n)$ defined by the recurrence
$$
U_k(n) = \begin{cases}
   U_k\left(\frac{n}{\log k}\right) + O(1) &amp; \text{if } n \ge k, 
   \\
   T(n) &amp; \text{otherwise.}\\
\end{cases}
$$
An easy inductive argument implies that $T(n) \le U_k(n)$ for any $k\le n$.  Assuming inductively that $T(n)$ is a nondecreasing function of $n$, the solution
$$
   U_k(n)
   \le T(k) + O\left( \frac{\log(n/k)}{\log \log k} \right)
$$
follows from standard methods.  Setting $k=\sqrt{n}$ gives us the simpler(?) recurrence
$$
   T(n) \le T(\sqrt{n}) + O\left( \frac{\log n}{\log \log n} \right),
$$
which is easy to solve by standard methods.</p>

<p>I'll walk through that one, too.  Multiply both sides by $\lg\lg n$:
$$
  T(n)\lg\lg n
  ~\le~ T(\sqrt{n})\lg\lg n + O(\log n)
  ~=~ T(\sqrt{n})(\lg\lg\sqrt{n} + 1) + O(\log n).
$$
Setting $LT(n) = T(n)\lg\lg n$ gives us
$$
  LT(n) \le LT(\sqrt{n}) + T(\sqrt{n}) + O(\log n).
$$
Assuming inductively that $T(n) \le 10^{10^{100}}\lg n$ for large enough $n$, the recurrence simplifies further to $LT(n) \le LT(\sqrt{n}) + O(\log n)$.  This recurrence expands into a geometric series, implying the solution $LT(n) = O(\log n)$, which implies $T(n) = O(\log n / \log\log n)$. </p>

<p>Hey look, all our inductive assumptions worked out!</p>

<p><strong>Short version:</strong> Logarithmic factors <em>usually</em> act like constants in recurrences, because they change so slowly.  The details are often grungy, but straightforward with a little practice.  (A glaring exception is the recurrence $T(n) = T(n/2) + \Theta(n/\log n)$, whose solution is  $T(n) = \Theta(n\log\log n)$.)</p>

CC BY-SA 3.0
2012-02-17T13:36:48.100Z
Super! I didn't understand one step along the way though - how to you get $U_k(n) \le T(k) + O(\log(n/k)\log \log k)$. I mean how do you get the 'k' in the denominator in the term $\log(n/k)$?
dhruvbird
CC BY-SA 3.0
2012-02-18T06:31:15.370Z
Starting with n, how many times do you have to divide by [whatever] until the result is less than k?
Jeffε
CC BY-SA 3.0
2012-02-17T09:51:26.307Z
2012-02-17T09:51:26.307Z
Jeffε
<p>$T(2) = T(1) = 1$</p>

<p>$T(n) = T(\frac{n}{\log n}) + \Theta(1)$</p>

<p>Basically, I wanted to know how many steps before the recursion stops?</p>

<p>I tried various approaches, but am not getting anywhere. <strike>I know for sure that this is $O((\log \log n)^2)$, but I wanted a $\Theta$ bound (tighter bound).</strike> (this analysis is incorrect as shown in the comments below).</p>

<p>I've also run a simple program to compare $n, T(n)$, and $\log \log n$.</p>

<pre><code>         n        T(n) log log n
             2,    1,    0
             4,    2,    1
             8,    3,    1
            16,    3,    2
            32,    4,    2
            64,    4,    2
           128,    5,    2
           256,    5,    3
           512,    5,    3
          1024,    5,    3
          2048,    6,    3
             .
             .
             .
     134217728,    9,    4
             .
             .
             .
 2199023255552,   12,    5
 4398046511104,   12,    5
 8796093022208,   12,    5
17592186044416,   13,    5
</code></pre>

<p>(This is not homework)</p>

CC BY-SA 3.0
2012-02-17T00:14:30.190Z
Assuming “O(1)” in the second formula is 1 and a floor function is missing around the fraction “n / log n”, I think that it is easy to prove a lower bound T(n) = Ω(log n / log log n), which contradicts the upper bound you claim in the question.  How did you prove the upper bound?
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-17T00:57:10.350Z
Yes, you are right. The trivial upper bound is incorrect. How did you prove the lower bound? (I am guessing that you just set k=log n and asked how many times to divide n by k to get 1?)
dhruvbird
CC BY-SA 3.0
2012-02-17T01:01:02.537Z
Yes, I obtained the lower bound that way.  (If you are asking how to turn that argument into a rigorous proof of the lower bound, one way to do so is by proving that T is monotonically increasing and using the mathematical induction.)
Tsuyoshi Ito
<ds.algorithms><time-complexity>
How many steps does this recurrence take to get to 2 (or 1)?
dhruvbird
# How many steps does this recurrence take to get to 2 (or 1)?

(Asked by: username_0 on 2012-02-16)

$T(2) = T(1) = 1$
$T(n) = T(\frac{n}{\log n}) + \Theta(1)$
Basically, I wanted to know how many steps before the recursion stops?
I tried various approaches, but am not getting anywhere. I know for sure that this is $O((\log \log n)^2)$, but I wanted a $\Theta$ bound (tighter bound). (this analysis is incorrect as shown in the comments below).
I've also run a simple program to compare $n, T(n)$, and $\log \log n$.
         n        T(n) log log n
             2,    1,    0
             4,    2,    1
             8,    3,    1
            16,    3,    2
            32,    4,    2
            64,    4,    2
           128,    5,    2
           256,    5,    3
           512,    5,    3
          1024,    5,    3
          2048,    6,    3
             .
             .
             .
     134217728,    9,    4
             .
             .
             .
 2199023255552,   12,    5
 4398046511104,   12,    5
 8796093022208,   12,    5
17592186044416,   13,    5

(This is not homework)

**Tags:** ds.algorithms, time-complexity
> **Comments:**
> **username_1**: Assuming “O(1)” in the second formula is 1 and a floor function is missing around the fraction “n / log n”, I think that it is easy to prove a lower bound T(n) = Ω(log n / log log n), which contradicts the upper bound you claim in the question.  How did you prove the upper bound?  
> **username_0**: Yes, you are right. The trivial upper bound is incorrect. How did you prove the lower bound? (I am guessing that you just set k=log n and asked how many times to divide n by k to get 1?)  
> **username_1**: Yes, I obtained the lower bound that way.  (If you are asking how to turn that argument into a rigorous proof of the lower bound, one way to do so is by proving that T is monotonically increasing and using the mathematical induction.)  

---

## 1 answers

### Answer by username_2 on 2012-02-17. Score: 10 | Accepted answer

The solution is $T(n) = \Theta(\log n /\log\log n)$. (I'm assuming the $O(1)$ term in the recurrence is really $\Theta(1)$, since otherwise $T(n)$ has no lower bound.)

As you and Tsuyoshi already observed, you can derive a lower bound by overestimating the denominator in the recursive argument. Consider the function $L\_k(n)$ defined by the recurrence
$$
L\_k(n) = L\_k\left(\frac{n}{\log k}\right) + \Theta(1).
$$
The solution $L\_k(n) = \Theta(\log n / \log \log k)$ follows from standard methods. An easy inductive argument implies that $T(n) \ge L\_k(n)$ for any $k\ge n$. Thus, setting $k=n^2$ (for example) immediately gives us $T(n) = \Omega(\log n/\log\log n)$.

For the upper bound, the symmetric trick is to *under*-estimate the denominator in the recursive argument. Consider the function $U\_k(n)$ defined by the recurrence
$$
U\_k(n) = \begin{cases}
U\_k\left(\frac{n}{\log k}\right) + O(1) & \text{if } n \ge k,
\\
T(n) & \text{otherwise.}\\
\end{cases}
$$
An easy inductive argument implies that $T(n) \le U\_k(n)$ for any $k\le n$. Assuming inductively that $T(n)$ is a nondecreasing function of $n$, the solution
$$
U\_k(n)
\le T(k) + O\left( \frac{\log(n/k)}{\log \log k} \right)
$$
follows from standard methods. Setting $k=\sqrt{n}$ gives us the simpler(?) recurrence
$$
T(n) \le T(\sqrt{n}) + O\left( \frac{\log n}{\log \log n} \right),
$$
which is easy to solve by standard methods.

I'll walk through that one, too. Multiply both sides by $\lg\lg n$:
$$
T(n)\lg\lg n
~\le~ T(\sqrt{n})\lg\lg n + O(\log n)
~=~ T(\sqrt{n})(\lg\lg\sqrt{n} + 1) + O(\log n).
$$
Setting $LT(n) = T(n)\lg\lg n$ gives us
$$
LT(n) \le LT(\sqrt{n}) + T(\sqrt{n}) + O(\log n).
$$
Assuming inductively that $T(n) \le 10^{10^{100}}\lg n$ for large enough $n$, the recurrence simplifies further to $LT(n) \le LT(\sqrt{n}) + O(\log n)$. This recurrence expands into a geometric series, implying the solution $LT(n) = O(\log n)$, which implies $T(n) = O(\log n / \log\log n)$.

Hey look, all our inductive assumptions worked out!

**Short version:** Logarithmic factors *usually* act like constants in recurrences, because they change so slowly. The details are often grungy, but straightforward with a little practice. (A glaring exception is the recurrence $T(n) = T(n/2) + \Theta(n/\log n)$, whose solution is $T(n) = \Theta(n\log\log n)$.)

> **Comments:**
> **username_0**: Super! I didn't understand one step along the way though - how to you get $U_k(n) \le T(k) + O(\log(n/k)\log \log k)$. I mean how do you get the 'k' in the denominator in the term $\log(n/k)$?  
> **username_2**: Starting with n, how many times do you have to divide by [whatever] until the result is less than k?  

---

