I'm currently using substitution method to solve recurrences. The problem I'm having is dealing with T(n) that have either ceilings or floors. For example in the following example see example here.
They end up using the guess:
T(n) ≧ c(n+2) lg(n+2)
My first guess was
T(n) ≧ n lg(n), which turns out to not work but my problem is I end up having to play around with guess to try get one to work. So questions are as follows:
- What is the best way to deal with these floors and ceiling in general?
- With regards to guesses, does this come with practice or are there betters ways of deducing the correct guess off the first shot without having to use Recursion Trees.
(PS not sure how to write equations in math notation, its my first time using this forum)