On ps7, how to go about determining the complexity of the recursive and iterative factorial algorithms? According to wikipedia(http://en.wikipedia.org/wiki/Factorial#Computation) the complexity of computing the factorial lies in storing the result. Storing the factorials of 5,6,7,8,9,10 takes, 7,10,13,16,19, and 22 bits, respectively. So it seems increasing the size of the input by 1 increases the bit count required for the solution by 3...but then after 12 or so, for each unit increase in the input the space required to store the solution increases by 4, i.e., storing 12! takes 29 bits and s

Question

On ps7, how to go about determining the complexity of the recursive and iterative factorial algorithms? According to wikipedia(http://en.wikipedia.org/wiki/Factorial#Computation) the complexity of computing the factorial lies in storing the result.  Storing the factorials of 5,6,7,8,9,10 takes, 7,10,13,16,19, and 22 bits, respectively. So it seems increasing the size of the input by 1 increases the bit count required for the solution by 3...but then after 12 or so, for each unit increase in the input the space required to store the solution increases by 4, i.e., storing 12! takes 29 bits and s

anonymous · Answer

Is there a difference in complexity between the iterative and recursive versions? I don't see it. Thank you.

anonymous · Answer

Both are O(N), but there actually is a difference between the two such that the recursive algorithm is slower than the iterative algorithm.

Try it and see for yourself, using the time() function imported from time.

anonymous · Answer

Thank you, hmmm, did you see a significant difference? I tried it with medium and large numbers, seems about the same. 99! takes about 26 miliseconds for both, 199! takes about 51 miliseconds for both.

anonymous · Answer

When you call a function, a stack is created. So when using iteration, you only create one stack. However, when you use recursion, stacks are made on top of stacks. This will eat up memory and infact slow down the performance of software to a certain degree. This might be irrelevant, but I wanted to share that with you.

anonymous · Answer

Great answer double_o_seven I think you are exactly right! The complexity of the recursive version lies in the size of the stack. See this great thread: http://stackoverflow.com/questions/33923/what-is-tail-recursion Every recursive call has to complete before the computer will do *any* calculation. fact0(5) would evaluate as fact0(5) 5*fact0(4) 5*4*fact0(3) 5*4*3*fact0(2) 5*4*3*2*fact0(1) 5*4*3*2*1 The computer can't multiply *anything* until the last recursive call (fact0(1)) is made. So it has to keep all those states in memory, so it's very costly that way. In fact when I tried to calculate fact0(995), it overflows: RuntimeError: maximum recursion depth exceeded while calling a Python object fact1() does not have that problem, I calculated fact1(10000), no problem.