Space Complexity

What is Space Complexity

The term space complexity is used to describe the amount of memory an algorithm requires during execution 1(https://books.google.co.uk/books?id=vdZ4Bm-LnHMC&lpg=PR5&ots=dnumo-wAe5&dq=W.%20Kuo%20and%20M.%20J.%20Zuo%2C%20Optimal%20reliability%20modeling%3A%20principles%20and%20applications.%20John%20Wiley%20%26%20Sons%2C%202003%20%2C%20p.%2062&lr&pg=PR5#v=onepage&q&f=false). The author of the web article titled "What does 'Space Complexity' mean " 2(https://www.geeksforgeeks.org/g-fact-86/) disagrees with W. Kuo and M. J. Zuo 1(https://books.google.co.uk/books?id=vdZ4Bm-LnHMC&lpg=PR5&ots=dnumo-wAe5&dq=W.%20Kuo%20and%20M.%20J.%20Zuo%2C%20Optimal%20reliability%20modeling%3A%20principles%20and%20applications.%20John%20Wiley%20%26%20Sons%2C%202003%20%2C%20p.%2062&lr&pg=PR5#v=onepage&q&f=false) definition of space complexity. The author of the web article 2(https://www.geeksforgeeks.org/g-fact-86/) explains that the definition of 'Auxillary space' and space complexity are often confused. It would seem that W. Kuo and M. J. Zuo 1(https://books.google.co.uk/books?id=vdZ4Bm-LnHMC&lpg=PR5&ots=dnumo-wAe5&dq=W.%20Kuo%20and%20M.%20J.%20Zuo%2C%20Optimal%20reliability%20modeling%3A%20principles%20and%20applications.%20John%20Wiley%20%26%20Sons%2C%202003%20%2C%20p.%2062&lr&pg=PR5#v=onepage&q&f=false) have given the definition of Auxillary space as the definition of space complexity. The web article 2(https://www.geeksforgeeks.org/g-fact-86/) claims that the actual definition for the term space complexity is the total space taken by the algorithm with respect to the input size.

During execution an algorithm will use memory space for three reasons 3(https://www.studytonight.com/data-structures/space-complexity-of-algorithms):

• Instruction Space - The amount of memory used to store the compiled version of instructions.
• Environmental Stack - When a function calls another function the current variables are pushed to the system stack while the other function is executed.
• Data Space - the amount of memory used to store variables and constants.

Much like Time Complexity, the Space complexity of an algorithm can also be represented in Big O notation.

References

[1] W. Kuo and M. J. Zuo, Optimal reliability modeling: principles and applications, John Wiley & Sons, 2003 , p. 62.

[2] https://www.geeksforgeeks.org/g-fact-86/

[3] https://www.studytonight.com/data-structures/space-complexity-of-algorithms