Local functions (nested functions) in Kotlin - Time & Space Complexity

Time Complexity: Local functions (nested functions)

O(n)

Understanding Time Complexity

We want to see how the time it takes to run code with local functions changes as the input grows.

How does nesting a function inside another affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun printNumbers(n: Int) {
    fun helper(i: Int) {
        if (i > n) return
        println(i)
        helper(i + 1)
    }
    helper(1)
}

This code prints numbers from 1 to n using a local (nested) recursive function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive call to helper that prints each number.
• How many times: It runs once for each number from 1 up to n, so n times.

How Execution Grows With Input

Each time we increase n, the function does one more print and recursive call.

Input Size (n)	Approx. Operations
10	About 10 prints and calls
100	About 100 prints and calls
1000	About 1000 prints and calls

Pattern observation: The work grows directly with n, adding one step per number.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Because the function is nested, it runs faster or slower than a normal function."

[OK] Correct: Nesting a function inside another does not change how many times it runs; only the number of calls matters.

Interview Connect

Understanding how local functions behave helps you explain recursion and function structure clearly, a useful skill in many coding discussions.

Self-Check

"What if the local function called itself twice each time instead of once? How would the time complexity change?"