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?

  • $\begingroup$ Note that $\log f(n) = \sqrt{2n}$. $\endgroup$ – Yuval Filmus Oct 27 '20 at 6:46
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 27 '20 at 6:46
  • $\begingroup$ The solution is most probably $T(n) = 2^{\Theta(\sqrt n)}$. I'm not sure what the hidden constant is. $\endgroup$ – Yuval Filmus Oct 27 '20 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.