1

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method?

I don't fully understand the theory of this method and I'm not sure how to apply it on this kind of recurrences; I'm a beginner in this field and i would like a simple solution that i could understand. Thank you!

Amzoti
  • 56,093
ViForU
  • 11
  • Do you want an exact solution, or do you want an approximation (e.g. big theta)? – apnorton Dec 09 '14 at 23:51
  • I want an approximation. I guess it will be: big theta(log n), but I'm not sure how to use the Substitution Method to check my guess. – ViForU Dec 10 '14 at 16:27

0 Answers0