Computer Science 2210A/B Lecture 4: Space Complexity

• School: Western University
• Department: Computer Science
• Course: Computer Science 2210A/B
• Professor: Roberto Solis- Oba

Document Summary

The space complexity of an algorithm measures the amount of memory that the algorithm needs to execute correctly. An algorithm will require memory to store any data structures that it uses and, if the algorithm is recursive, it will also require memory to store the execution stack. To illustrate how to compute the space complexity of an algorithm, let us consider the following algorithm that computes the height of a tree. Out: height of the tree if r is a leaf then return 0 else { max height 0 for each child ri of r do { H height (ri) if h >max height then max height h return max height + 1 (a1) The above algorithm needs memory to store the input tree. If we assume that each node requires a constant amount c of space, then if the tree has n nodes the amount of space needed to store it is cn, which is o(n).