Environment and closures in R Programming - Time & Space Complexity

Time Complexity: Environment and closures

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with environments and closures changes as we use more data or call functions more times.

How does the work grow when closures keep variables inside and functions run repeatedly?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

make_counter <- function() {
  count <- 0
  function() {
    count <<- count + 1
    count
  }
}

counter <- make_counter()
for (i in 1:5) {
  print(counter())
}
    

This code creates a counter function that remembers how many times it was called and increases the count each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the inner function that updates and returns the count.
• How many times: The inner function is called once per loop iteration, here 5 times.

How Execution Grows With Input

Each call to the closure does a simple update and return. The work grows directly with how many times we call it.

Input Size (n)	Approx. Operations
10	10 simple updates
100	100 simple updates
1000	1000 simple updates

Pattern observation: The work grows evenly as we call the function more times.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the number of times we call the closure.

Common Mistake

[X] Wrong: "Closures make the code slower because they keep all past values and slow down over time."

[OK] Correct: The closure only updates one variable each time, so the work per call stays the same no matter how many calls happen.

Interview Connect

Understanding how closures keep data and how calling them scales helps you explain how functions remember things without slowing down unexpectedly.

Self-Check

"What if the closure stored all past counts in a list instead of a single number? How would the time complexity change?"