where n is the size of the input. There's a nice theorem for generating closed form solutions to these. However, if you start messing with the recurrence a bit, things can get ugly quickly. For example, in our last homework we had:
No theorem for this guy. So, the next best thing is to take a stab at the solution and then try to prove you're right by substituting the answer back into the recurrence. All good, but how do you guess the solution? Is it at all obvious that the above recurrence is
The standard tactic is to build a recursion tree, figuring that a visual representation of what's going on might help steer you the right way. Again, it didn't help me much. However, recursion trees are a tool developed back in the 40's when the thought of actually computing these functions recursively was a non-starter. Now, it's easy. It took me less time to create a spreadsheet that calculated the first million values than it did to draw a useless recursion tree. Once I had the values, it was a fairly simple matter of matching the curve to various functions of n to get an asymptotic bound. Once I had the bound, I realized how I could redraw the tree to suggest such an answer (I wouldn't have bothered with that step except that the homework called for it). Sticking it into the recurrence and proving that it worked was pretty straightforward.
I think recursion trees are a useful tool for understanding the concept. They may also be of use in explaining why a solution works. But, anybody who's using them to actually solve non-trivial problems is really wasting their time.
No comments:
Post a Comment