Memoize only reduces the work, it doesn't eliminate checking to see if it's already done.

For N=1000, 2^n ~~ 1e301, while n^2/2 ~~ 1e5. The first will never finish in the lifetime of the universe, the second in a blink of an eye.