Define Big-O for space complexity and give an example of a function with O(n) space.

• A. Time complexity measures memory usage growth; e.g., looping n times uses O(n) space.
• B. Big-O space complexity measures memory usage growth; e.g., storing n items in an array uses O(n) space.
• C. Big-O space complexity disregards input size.
• D. O(n) space means constant memory.

Answer: (B)

Big-O space complexity describes how much extra memory a program needs as the input size grows, focusing on how memory usage scales with n. An example that fits this idea is storing n items in an array: as n increases, the memory required grows proportionally to n, so the space usage is O(n). It’s different from time complexity, which concerns how the running time grows, not how much memory is used. A loop that runs n times can take O(n) time but may still use only a constant amount of extra space if it doesn’t allocate memory per iteration. The notion of space complexity accounts for how memory grows with input size, so it isn’t about ignoring input size or about constant memory. O(n) space means memory grows linearly with n, not that it’s fixed.