1

In my Data Structures Class, we're looking at recurrence relations like T(n) and big O problems O(n). I'd appreciate any resources for learning these, my textbook doesn't cover T(n), and the professor skips over lots of steps.

I haven't seen a good, step-by-step method for solving these things. I realize that every problem is unique, but there has to be some sort of framework for doing these.

Thanks.

Jeremy
  • 11
  • 2
  • A good place to start is this [SO discussion][1]. [1]: http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on – DavidC Oct 01 '11 at 17:56

2 Answers2

1

Check Concrete Mathematics - A Foundation for Computer Science, it's a brilliant book with lots of examples and exercises.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
1

Another great book is Introduction to Algorithms. It has a pretty thorough section on solving recurrence relations.

You are right, there is a generalized method for solving simple recurrence relations called the Master Theorem. (The explanation in Introduction to Algorithms is much better than the Wikipedia page.) It doesn't work for every case, but it solves a lot of common ones.

japreiss
  • 11,111
  • 2
  • 40
  • 77