If we account for arbitrary precision operations necessary for large N, I believe the memoized insane recursion is quadratic in space and time. This is actually not as bad of a pessimization as I thought it would be over just using Binet's formula, but it's still a hit.