Analysis of the complexity of a recursive algorithm
Throughout the chapter, I have conveniently skipped over the complexity analysis of the algorithms I have discussed. This was to ensure that you grasp the concepts of functional programming before being distracted by something else. Now is the time to get back to it.
Analyzing the complexity of a recursive algorithm involves first creating an equation. This is naturally the case because the function is defined in terms of itself for a smaller input, and the complexity is also expressed as a function of itself being calculated for a smaller input.
For example, let's say we are trying to find the complexity of the
foldLeft operation. The
foldLeft operation is actually two operations, the first one ...