A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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