T(n) = T(n - sqrt(n))

Question

Does anyone know how to solve this recurrence?

Master Theorem doesn't work here.

Answer 1

It seems obvious in O(1) since

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

By induction, you get T(n) = T(epsilon) with epsilon close to 0.

The question make more sens if it was T(n) = T(n - sqrt(n)) + m

Answer 2

You are right that the Masters theorem does not apply here. If you will look closer, you will see that the cost of recursion is zero (there is no free element on the right side: T(n) = T(m) + f(n).

This means that it costs you absolutely nothing to run your recursion (not even 1 operation). So as long as your n decreases over iterations (and it does because n > n - sqrt(n)) your recursion is actually free.

So the answer is O(1). P.S. it is not possible to have this in real life because you will do at least O(1) as the cost of recursion.