Function references (::functionName) in Kotlin - Time & Space Complexity

Time Complexity: Function references (::functionName)

O(n)

Understanding Time Complexity

We want to understand how using function references affects the time it takes for a program to run.

Specifically, does calling a function by reference change how long the program takes as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun square(x: Int): Int = x * x

fun applyFunction(numbers: List, f: (Int) -> Int): List {
    return numbers.map(f)
}

val nums = List(1000) { it }
val squares = applyFunction(nums, ::square)
    

This code applies a function reference (::square) to each number in a list to create a new list of squares.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The map function loops over each element in the list.
• How many times: Once for each element in the input list.

How Execution Grows With Input

As the list size grows, the number of times the function is called grows the same way.

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

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using a function reference (::square) makes the program slower because it adds extra overhead."

[OK] Correct: Calling a function by reference is just a way to pass the function; it does not add extra loops or repeated work. The main cost is still from looping over the list.

Interview Connect

Understanding how function references work helps you explain code clearly and reason about performance in real projects.

Self-Check

"What if the function passed was more complex and took longer to run? How would that affect the time complexity?"