One Pager Cheat Sheet

• We will learn how to calculate space complexity by considering two main factors: Input space and Auxiliary space.
• Space complexity is generally represented using big O notation to express how the space requirements of a program grow with the change in the size of the inputs.
• The space complexity of a recursive algorithm is dependent on the maximum number of activation records on the stack, as well as the variables being passed by reference or value.
• Recursion can require more memory than other algorithms, and stack overflow errors can occur without appropriate control due to activation records and copying of arguments for each call.
• The iterative solution of computing a factorial has a space complexity of O(1), while the recursive solution has a space complexity of O(n).
• The algorithm sumElements has a space complexity of O(n), since the number of iterations of the loop is equal to the size of the array.
• Binary search is a sorting algorithm used to find a value in an array with a space complexity of O(n) using either an iterative or recursive solution.
• The overall space complexity for a depth-first traversal to detect a cycle in a graph represented by an adjacency matrix with n nodes is O(n).
• The space complexity of sorting algorithms can range from O(1) to O(n) and is often dependent on the implementation.
• It is not possible to reduce the space complexity of an algorithm by reducing the number of computations, as the amount of memory needed is determined by the algorithm and the data structures used.
• Choosing between iterative or recursive approaches can greatly affect the space complexity of the algorithm, which should be a key consideration when designing and implementing programs.