Closures and variable capture in Kotlin - Time & Space Complexity

Time Complexity: Closures and variable capture

O(n)

Understanding Time Complexity

Let's explore how the time cost grows when using closures that capture variables in Kotlin.

We want to see how the number of operations changes as input size grows when closures remember variables.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun createFunctions(n: Int): List<() -> Int> {
    val funcs = mutableListOf<() -> Int>()
    for (i in 0 until n) {
        val capturedI = i
        funcs.add { capturedI * 2 }  // closure captures capturedI
    }
    return funcs
}

fun main() {
    val functions = createFunctions(5)
    functions.forEach { println(it()) }
}
    

This code creates a list of functions, each capturing the loop variable i.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A loop runs n times to create n closures.
• How many times: The loop runs once for each number from 0 to n-1.

How Execution Grows With Input

Each time n grows, the loop runs more times, creating more closures.

Input Size (n)	Approx. Operations
10	10 closures created
100	100 closures created
1000	1000 closures created

Pattern observation: The work grows directly with n. Double n, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create all closures grows in a straight line with the number of closures you want.

Common Mistake

[X] Wrong: "Closures run instantly and don't add to time because they just remember variables."

[OK] Correct: Creating each closure takes time because it stores the current variable value. More closures mean more work.

Interview Connect

Understanding how closures capture variables and how that affects time helps you explain how your code scales when using functions inside loops.

Self-Check

"What if the closure captured a variable that changes inside the loop instead of the loop variable itself? How would that affect time complexity?"