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 ...

Get Java 9 Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.