Solve a recurrence with $n/\log n$

Question

Here is the question:

Let $T(n) = T(\frac{n}{\log_2(n)}) + 1$. Solve for $T(n).$

The answer is $T(n) = \Theta(\frac{\log_2(n)}{\log_2{\log_2 (n)}})$.

First of all what is the valid choice for $n$? The expression $f(n) = \frac{n}{\log_2(n)}$ should be a natural number. If we set $n = 2^{2^x}$, then $f(n)$ is a natural number but in the next level it could be non-integer. For example $n= 256$ leads to $n = 8$ and then $f(8) = \frac{8}{3}$ which is nonsense for $T(\frac{8}{3})$ isn't defined. Also I couldn't solve the recurrence.

Note: Master Theorem isn't eligible.

Answer 1

Calling $\log_2 n = a_n$ and considering $a_n > 0$

$$ T\left((a_n)^{\log_{a_n}n}\right)=T\left((a_n)^{\log_{a_n}n-1}\right)+1 $$

Calling now $\mathbb{T}(\cdot)=T\left((a_n)^{(\cdot)}\right)$ and $z = \log_{a_n}n$ we have the recurrence

$$ \mathbb{T}(z)=\mathbb{T}(z-1)+1 $$

with solution

$$ \mathbb{T}(z)=C_0(z)+z $$

with $C_0(z)$ a generic periodic function with period $1$ that we will assume constant, or backwards

$$ T(n) = C_0 + \frac{\log_2 n}{\log_2(\log_2 n)} $$

hence

$$ T(n) = \Theta\left(\frac{\log_2 n}{\log_2(\log_2 n)}\right) $$

NOTE

for $a > 0, b > 0$ $$ b = a^{\log_a b} $$

Answer 2

We often see recurrences like this, coming from computer science. But (as we see from the OP) they normally do not have enough explanation to become a mathematical problem. In this case, even if $n$ is an integer, it need not follow that $n/\log_2 n$ is an integer.

Here is one guess as to how this one should be formulated: Suppose $T : [a,+\infty) \to (0,+\infty)$ is a sufficiently regular function. [Meaning perhaps continuous, monotonic, $C^1$, $C^\infty$, analytic, or ...] Suppose $$ T(x) = T\left(\frac{x}{\log_2 x}\right) + 1\qquad \text{for all }x \in [a,\infty) \text{ such that } \frac{x}{\log_2 x} \in [a,+\infty). $$ Then $$ T(x) = \Theta\left(\frac{\log_2 x}{\log_2\log_2 x}\right)\qquad\text{as } x \to +\infty. $$ A solution would mention what regularity is assumed.

Answer 3

I don't think there is a way to solve the recurrence exactly.

If we iterate,

$$T(n)=T\left(\frac n{\lg(n)}\right)+1 \\=T\left(\frac n{\lg(n)(\lg(n)-\lg(\lg(n)))}\right)+2$$

we can approximate as

$$\approx T\left(\frac n{\lg^2(n)}\right)+2$$

and inductively

$$\approx T\left(\frac n{\lg^k(n)}\right)+k.$$

Now we can estimate $k$ by imposing that the argument of $T$ reaches a constant value, say $1$, so that

$$n\approx\lg^k(n),$$ or

$$k\approx\frac{\lg(n)}{\lg(\lg(n))}.$$

---

This is only meant to give some insight in the behavior of $T(n)$ and now remains to formally verify

$$T(n)=\Theta\left(\frac{\lg(n)}{\lg(\lg(n))}\right),$$ i.e. there are two constants such that

$$C_0\dfrac{\lg(n)}{\lg(\lg(n))}\le T(n)\le C_1\dfrac{\lg(n)}{\lg(\lg(n))}$$ for sufficiently large $n$.