Answer to Question #259261 in Algorithms for anju

Question

What is space complexity? Discuss various factors affecting it. Write iterative and recursive algorithm of finding factorial of a given number and find its space complexity.

Answer 1

The space complexity of an algorithm determines how much additional memory is required to execute this algorithm.

Additional memory may be required for additional variables used in the algorithm, and the size of these variables may be determined by the input data size (for example, the algorithm may require to create a copy of the input array). Also, when considering recursive algorithms, it is necessary to take into account the fact that with each call of a function, local copies of the variables (as well as its parameters) belonging to this function are created.

Iterative function:

function factorial(n)
set res = 1
for i from 2 to n do
  res = res * i
return res

The space complexity of this algorithm is O(1), as the size of additional variables (i and res) is independent of the input data (n)

Recursive function:

function factorial(n)
if n equal 1
  return 1
return n * factorial(n-1)

The space complexity of this algorithm is O(n), as the function factorial is called n times and each call creates a copy of the function's parameter n.