O'Reilly logo

How to Think About Algorithms by Jeff Edmonds

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

27 Recurrence Relations

A wise man told the king to give him one grain of rice one for the first square of a chessboard and for the each remaining square to give him twice the number for the previous square. Thirty-two days later, the king realized that there is not enough rice in all of world to reward him. The number of grains on the nth square is given by the recurrence relation T(1) = 1 and T(n) = 2T(n − 1).

The algebraic equation x2 = x + 2 specifies the value of an unknown real that must be found. The differential equation image specifies functions from reals to reals that must be found. Similarly, a recurrence relations like T(n) = 2 × T(n − ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required