The Efficiency of Recursion

In our second, improved version of the max function, the function recursively calls itself as many times as there are values in the array. We’d call this O(N).

Up until this point, the cases of O(N) we’ve seen involved loops, with a loop running N times. However, we can apply the same principles of Big O to recursion as well.

As you’ll recall, Big O answers the key question: if there are N data elements, how many steps will the algorithm take?

Since the improved max function runs N times for N values in the array, it has a time complexity of O(N). Even if the function itself contains multiple steps, such as five, its time complexity would be O(5N), which is reduced to O(N).

In the first version, though, the function called itself twice during each run (save for the base case). Let’s see how this plays out for different array sizes.

The following table shows how many times max gets called on arrays of various sizes:

Can you see the pattern? When we increase the data by one, we roughly double the number of steps the algorithm takes. As you learned by our discussion of the , this is the pattern of O(2^N). We already know that this is an extremely slow algorithm.

The improved version of the max function, however, only calls max for as many elements as there are inside the array. This means that our second max function has an efficiency of O(N).

This is a powerful lesson: avoiding extra recursive calls is key to keeping recursion fast. What at first glance was a very small change to our code—the mere storing of a computation in a variable—ended up changing the speed of our function from O(2^N) to O(N).