Recurrence $T(n) = T(n - \log n) + 1$ Given recurrence relation : $$
T(n) = \begin{cases}
   T(n-\log n) + 1 &amp; \text{if } n \ge 1, 
   \\
   1 &amp; \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)$.