Higher-order function declaration in Kotlin - Time & Space Complexity

Time Complexity: Higher-order function declaration

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a higher-order function changes as the input grows.

Specifically, how does calling a function that takes another function affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun applyToList(numbers: List<Int>, operation: (Int) -> Int): List<Int> {
    val result = mutableListOf<Int>()
    for (num in numbers) {
        result.add(operation(num))
    }
    return result
}

This function takes a list of numbers and another function, then applies that function to each number in the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the list and applying the passed function.
• How many times: Once for every item in the input list.

How Execution Grows With Input

As the list gets bigger, the function inside runs more times, once per item.

Input Size (n)	Approx. Operations
10	10 calls to the operation function
100	100 calls to the operation function
1000	1000 calls to the operation function

Pattern observation: The work grows directly with the number of items; doubling the list doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items in the list.

Common Mistake

[X] Wrong: "Since the function is passed in, it runs instantly or doesn't add to the time."

[OK] Correct: Each call to the passed function still takes time, so the total time depends on how many times it runs.

Interview Connect

Understanding how higher-order functions affect time helps you explain your code clearly and reason about performance in real projects.

Self-Check

"What if the passed function itself contains a loop over the input list? How would the time complexity change?"