Usage of Difference Equations(recurrence relations) in IT fields

Question

I'm doing a IT diploma and Mathematics also be tought there.In these days, we have to learn Difference Equations(recurrence relations) and I'm confused with what are the usages of these concepts in different areas of IT like computing, algorithms and data structures, circuit analysis, etc.

Can someone please explain why we learn these concepts and usage of them. It will be helpful my learnings.

Answer 1

Unutbu has an excellent explanation and link to what is a recurrence relation. Here is a small window into the why.

Computer scientists need to know how algorithms compare to one another (in terms of speed or memory space). The Recurrence Relations help provide this comparison (on an order of magnitude).

Here is a general question: How many possible moves in chess are there? If there are 318 billion moves (for the first four), could you use an exhaustive algorithm to search for the best, first move? If that is impractical, what algorithms might trim that to a reasonable size? The complexity measures give us an insight into the difficulty of the problem and into the practicality of a given algorithm.

Answer 2

Recurrence relations come up in complexity theory. The number of steps performed by a recursive algorithm can be expressed as a recurrence relation, such as

The goal then is to express T as (or bound T by) a (hopefully simple) function of n.

The master theorem is one example of how this is done.