Efficiency

Memoization is a technique to increase the efficiency of a program. The main idea is the remember the results that have been computed before, such that we don't need to waste time computing them again later.

Usually, this is achieved by using some type of cache, often implemented as a dictionary, to store previous results. This can speed up computation of functions such as the Fibonacci sequence.

We can roughly define the efficiency of functions by categorizing them based on how computationally expensive it gets as the size of the input grows, known as its order of growth. Functions that grow linearly take linear time, functions that grow according to a quadratic take quadratic time, and so on.

There are several common orders of growth:

1. Exponential growth: incrementing \(n\) multiplies the time by a constant.
2. Quadratic growth: incrementing \(n\) increases time by \(n\) times a constant.
3. Linear growth: incrementing \(n\) increases time by a constant.
4. Logarithmic growth: doubling \(n\) only increments time by a constant.
5. Constant growth: inrceasing \(n\) doesn't affect time.

Space, or memory, is another resource that can be optimized. Frames and the objects stored in them in active environments take up space. Active environments can be environments for any function calls currently being evaluated, as well as parent environments of functions named in active environments.