Space Complexity

This section covers the space complexity of algorithms and how it affects the memory usage of a program.

Definition

Space complexity measures the amount of memory space required by an algorithm as a function of the input size.

Components of Space Complexity

  1. Fixed Part: Memory needed for constants and variables.
  2. Variable Part: Memory required by dynamic data structures like arrays and recursion stacks.

Examples

  • Recursive algorithms may require extra space for the call stack.
  • Sorting algorithms like Merge Sort require O(n) extra space, while Quick Sort requires O(log n).