Is The Big O Notation The Same For Memoized Recursion Versus Iteration?

I am using a simple example off the top of my head here function factorial(n) if n==1 return 1 else return n*factorial(n-1) function factorial(n) result = 1 for i =

Solution 1:

Generally when considering an algorithm's complexity we would consider space and time complexity separately.

Two similar algorithms, one recursive, and one converted to be not recursive will often have the same time complexity, but differ in space complexity.

In your example, both factorial functions are O(n) time complexity, but the recursive version is O(n) space complexity, versus O(1) fort he iterative version.

This difference isn't universal. Memoization take space, and sometimes the space it takes up is comparable or even greater than the stack space a recursive version uses.

Solution 2:

Depending on the complexity of what you're using to store memoized values, the two will have the same order of complexity. For example, using a dict in Python (which has (amortized) O(1) insert/update/delete times), using memoization will have the same order (O(n)) for calculating a factorial as the basic iterative solution.

However, just as one can talk about time complexity, one can also talk about space complexity. Here, the iterative solution uses O(1) memory, while the memoized solution uses O(n) memory.

Solution 3:

If you are talking about asymptotically time complexcity, of course it's the same cause you are using the same algorithm. I guess what you really care about is performance. For C like language, it is possible that recursion will be more expensive.

Solution 4:

Are you going to actually use the memoized results? Besides the fact that the order is the same (both scale equivalently), for a single run of factorial, memoizing is useless - you'll walk through a series of arguments, and none of them will repeat - you'll never use your saved memoized values, meaning that you'll have wasted space and time storing them, and not gotten any speed-ups anywhere else.

However... once you have your memoized dictionary, then subsequent factorial calls will be less than O(n), and will depend on the history. I.E. if you calculate factorial(10), then values of factorial between 10 and 0 are available for instant lookup - O(1). If you calculate factorial(15), it does 15*14*13*12*11*factorial(10), which it just looks up, for 6 multiplies total (instead of 15).

However, you could also create a lookup dict for the iterative version, I guess. Memoization wouldn't help as much - in that case, factorial(10) would only store the result for 10, not all the results down to 0, because that's all the argument list would see. But, the function could store those intermediate values to the memoization dict directly.