开发者

Recurrence Relations in Data Structures

开发者 https://www.devze.com 2023-04-09 11:01 出处：网络

In my Data Structures Cla开发者_如何学Goss, 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),

相关专题：data-structures math recurrence

In my Data Structures Cla开发者_如何学Goss, 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.

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

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.