# Solving a recurrence in which $n$ decreases by $\sqrt{2n}$

I'm trying to solve the recurrence $$T(n)= 2T(n-\log f(n))+ f(n)$$, where $$f(n) = 2^{\sqrt{2n}}$$, using the master theorem. Which case applies here?

• Note that $\log f(n) = \sqrt{2n}$. – Yuval Filmus Oct 27 '20 at 6:46
• Your recurrence matches no case of the master theorem, which deals with a different kind of recurrence. The master theorem solves many recurrences which occur in practice, but not all of them. – Yuval Filmus Oct 27 '20 at 6:46
• The solution is most probably $T(n) = 2^{\Theta(\sqrt n)}$. I'm not sure what the hidden constant is. – Yuval Filmus Oct 27 '20 at 6:47