Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$.
