Recurrence $T(n) = T(n - \log n) + 1$

Question

Given recurrence relation : $$ T(n) = \begin{cases} T(n-\log n) + 1 & \text{if } n \ge 1, \\ 1 & \text{otherwise.}\\ \end{cases} $$

To find asymptotic order of $T(n)$ i do as follow:

Suppose $n=\log m$ now :

$$T(\log m)=T(\log m-\log \log m) +1$$

$$\implies T(\log m)= T(\log \frac{m}{\log m}) +1$$

,but in this step i get stuck and i don't know how we can transfer relation to get easier relation.

Answer 1

Let $n_0 = n$ and $n_{i+1} = n_i - \log n_i$. Then $T(n)$ is one plust the minimal $t$ such that $n_t \leq 1$.

Clearly $n_{i+1} \geq n_i - \log n$, hence $n_t \geq n - t\log n$, implying that $T(n) \gtrsim n/\log n$.

In the other direction, as long as $n_i \geq \sqrt{n}$, the sequence decreases by at least $\tfrac{1}{2} \log n$, hence it takes at most 2ドルn/\log n$ steps to get down from $n$ to $\sqrt{n}$. After at most 4ドル\sqrt{n}\log n$ steps, we get down to $\sqrt[4]{n}$; and so on. If we carefully count the steps, we see that $T(n) = O(n/\log n)$. Hence $T(n) = \Theta(n/\log n)$.