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

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.

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 $$2n/\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)$$.