As far as I know There are 4 ways to solve recurrence equations : 1- Recursion trees 2- Substitution 3 - Iteration 4 - Derivative
We are asked to use Substitution, which we will need to guess a formula for output. I read from CLRS book that there is no magic to do this, i was curious if there are any heuristics to do this?
I can certainly have an idea by drawing a recurrence tree or using iteration but, because the output will be in Big-OH or Theta format, formulas doesnt necessarily match.
Does any one have any recommendation for solving recurrence equations using substitution?
For simple ones, just take a "reasonable" guess.
For more complicated ones, I would go ahead and use a recurrence tree — it seems to me to be the easiest "algorithm" for generating a guess. Note that it can be difficult to use a recurrence tree to prove a bound (the details are tough to get right). Recurrence trees are highly useful for forming guesses which are then proven by substitution.
I'm not sure why you're saying the formulas won't match with the output in Big-O or Theta. They typically don't match exactly, but that's part of the point of Big-O. Part of the trick of going back to substitution is knowing how to plug in the Big-O solution to to make the substitution algebra work out. IIRC, CLRS does work out an example or two of this.