Linear Space: O(n)
You'll learn what it means when an algorithm uses memory proportional to the size of its input.
The Core Idea
An algorithm has O(n) space complexity when the amount of extra memory it needs grows linearly with the input size. If you double the input, you roughly double the memory used.
Think of it like photocopying a book: copying a 100-page book requires 100 sheets of paper, copying a 200-page book requires 200 sheets. The paper needed scales directly with the number of pages.
Common O(n) Space Patterns
Copying arrays is the classic example. If you have an array with n elements and you create a complete copy, you need storage for n new elements:
Original array: [1, 2, 3, 4, 5] // uses n memory slots
Copy array: [1, 2, 3, 4, 5] // uses another n slots
Total auxiliary space: O(n)
Creating temporary arrays during processing also exhibits O(n) space:
- Building a result array of the same size as input
- Storing intermediate values for each input element
- Maintaining a frequency count for every unique input item
Why It Matters
O(n) space is considered efficient for many problems where you genuinely need to process or transform every element. It's vastly better than O(n²) or worse. However, when possible, O(1) solutions (using only a fixed amount of extra memory) are preferred because they don't grow with input size.
Key Takeaway: O(n) space complexity means your algorithm's memory usage grows linearly with input size—common when copying data structures or building output arrays equal in size to the input.