Space complexity analysis in Data Structures Theory - Time & Space Complexity

Time Complexity: Space complexity analysis

O(n)

Understanding Time Complexity

We want to understand how much extra memory a program uses as the input size grows.

The question is: how does the space needed change when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function createArray(n) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}
    

This code creates an array and fills it with numbers from 0 up to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding one item to the array inside a loop.
• How many times: Exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the array grows by one item each time the loop runs.

Input Size (n)	Approx. Memory Used (items)
10	10 items
100	100 items
1000	1000 items

Pattern observation: Memory use grows directly with input size; doubling n doubles memory needed.

Final Time Complexity

Time Complexity: O(n)

This means the memory needed grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "The memory used stays the same no matter how big n is."

[OK] Correct: Since the array stores n items, more input means more memory is needed.

Interview Connect

Understanding how memory grows with input helps you write programs that use resources wisely and avoid crashes.

Self-Check

What if the code created a two-dimensional array with n rows and n columns? How would the memory use change?