A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Little Fix for Big O

Thankfully, there’s an easy way to eliminate all these extra recursive calls. We’ll call max only once within our code, and save the result to a variable:

def max(array)

  return array[0] if array.length == 1

  # Calculate the max of the remainder of the array
  # and store it inside a variable:

  max_of_remainder = max(array[1, array.length - 1])

  # Comparison of first number against this variable:

  if array[0] > max_of_remainder
    return array[0]
  else
    return max_of_remainder
  end
end

By implementing this simple modification, we end up calling max a mere four times. Try it out yourself by adding the puts "RECURSION" line and running the code.

The trick here is that we’re ...