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?"

Practice

1. What does the Kotlin syntax ::functionName represent?

easy

A. A call to the function named functionName

B. A comment about the function named functionName

C. A variable declaration named functionName

D. A reference to the function named functionName

Solution

1. Step 1: Understand the :: operator in Kotlin

   The :: operator is used to get a reference to a function, not to call it.

2. Step 2: Differentiate between calling and referencing

   Calling a function uses parentheses like functionName(), while referencing uses ::functionName.

3. Final Answer:

   A reference to the function named functionName -> Option D

4. Quick Check:

   Function reference = ::functionName [OK]

Hint: Remember :: means 'point to function', not call it [OK]

Common Mistakes:

• Confusing function reference (::) with function call (())
• Thinking :: declares a variable
• Assuming :: is a comment or annotation

2. Which of the following is the correct syntax to pass a function reference to map in Kotlin?

easy

A. list.map(::functionName)

B. list.map(:functionName)

C. list.map(functionName())

D. list.map(functionName)

Solution

1. Step 1: Identify how to pass function references in Kotlin

   Function references use the :: operator before the function name when passed as arguments.

2. Step 2: Check each option for correct syntax

   list.map(::functionName) uses ::functionName, which is the correct way to pass a function reference to map.

3. Final Answer:

   list.map(::functionName) -> Option A

4. Quick Check:

   Pass function reference with :: [OK]

Hint: Use :: before function name when passing as argument [OK]

Common Mistakes:

• Passing function call instead of reference (using parentheses)
• Omitting :: operator
• Using incorrect single colon : instead of double ::

3. What is the output of this Kotlin code?

fun square(x: Int) = x * x
val numbers = listOf(1, 2, 3)
val squares = numbers.map(::square)
println(squares)

medium

A. [1, 4, 9]

B. [square, square, square]

C. [1, 2, 3]

D. Compilation error

Solution

1. Step 1: Understand the function reference usage

   The ::square passes the square function to map, which applies it to each element.

2. Step 2: Calculate the result of applying square to each number

   Applying square to 1, 2, 3 gives 1, 4, 9 respectively.

3. Final Answer:

   [1, 4, 9] -> Option A

4. Quick Check:

   map(::square) squares each element [OK]

Hint: map(::function) applies function to each list item [OK]

Common Mistakes:

• Expecting original list instead of transformed list
• Confusing function reference with function call
• Thinking output is function names instead of results

4. Identify the error in this Kotlin code snippet:

fun greet(name: String) = "Hello, $name"
val greeter = greet
println(greeter("Alice"))

medium

A. Missing parentheses when assigning function reference

B. Cannot assign function directly without :: operator

C. Function greet must return Unit

D. No error, code runs fine

Solution

1. Step 1: Check how function references are assigned

   Assigning a function to a variable requires the :: operator to get a reference.

2. Step 2: Identify the missing :: operator

   The code assigns greet instead of ::greet, causing a type mismatch error.

3. Final Answer:

   Cannot assign function directly without :: operator -> Option B

4. Quick Check:

   Use :: to assign function reference [OK]

Hint: Use :: when assigning function to variable [OK]

Common Mistakes:

• Assigning function name without ::
• Adding parentheses which calls function instead of referencing
• Assuming function must return Unit

5. Given this Kotlin code, what will be the output?

fun isEven(n: Int) = n % 2 == 0
val numbers = listOf(1, 2, 3, 4, 5, 6)
val evenNumbers = numbers.filter(::isEven)
println(evenNumbers)

Choose the correct output and explain why function references are useful here.

hard

A. [true, false, true, false, true, false]

B. [1, 3, 5]

C. [2, 4, 6]

D. Compilation error due to filter usage

Solution

1. Step 1: Understand the function reference with filter

   The ::isEven passes the isEven function to filter, which keeps elements where the function returns true.

2. Step 2: Apply isEven to each number and filter

   Numbers 2, 4, and 6 are even, so they remain in the filtered list.

3. Step 3: Explain usefulness of function references

   Function references let us pass existing functions easily without writing extra lambdas.

4. Final Answer:

   [2, 4, 6] -> Option C

5. Quick Check:

   filter(::isEven) keeps even numbers [OK]

Hint: filter(::function) keeps items where function returns true [OK]

Common Mistakes:

• Confusing filter with map output
• Expecting boolean list instead of filtered list
• Not using :: for function reference