CODEWITHSUNDEEP
mathdata-structuresrecurrence
Jeremy
Jeremy

Reputation: 11

Recurrence Relations in Data Structures

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.

Upvotes: 1

Views: 1239

Answers (2)

japreiss
japreiss

Reputation: 11251

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.

Upvotes: 1

Karoly Horvath
Karoly Horvath

Reputation: 96258

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

Upvotes: 1

Related Questions