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

Practice

1. What is a higher-order function in Kotlin?

easy

A. A function that only returns integers

B. A function that takes another function as a parameter or returns a function

C. A function that cannot be called directly

D. A function that has no parameters

Solution

1. Step 1: Understand the definition of higher-order functions

   Higher-order functions are functions that can take other functions as parameters or return them as results.

2. Step 2: Match the definition with the options

   A function that takes another function as a parameter or returns a function correctly describes this behavior, while others describe unrelated function properties.

3. Final Answer:

   A function that takes another function as a parameter or returns a function -> Option B

4. Quick Check:

   Higher-order function = function with function parameter or return [OK]

Hint: Remember: higher-order means function uses another function [OK]

Common Mistakes:

• Thinking higher-order means function returns only numbers
• Confusing higher-order with functions without parameters
• Assuming higher-order functions cannot be called directly

2. Which of the following is the correct syntax to declare a higher-order function in Kotlin that takes a function parameter returning Int?

easy

A. fun operate(x: Int, f: Int): Int { return f(x) }

B. fun operate(x: Int, f: (Int) Int): Int { return f(x) }

C. fun operate(x: Int, f: (Int) -> Int): Int { return f(x) }

D. fun operate(x: Int, f: (Int) -> Int) { return f(x) }

Solution

1. Step 1: Identify correct function type syntax

   Kotlin uses (Type) -> ReturnType to declare function types. fun operate(x: Int, f: (Int) -> Int): Int { return f(x) } uses (Int) -> Int correctly.

2. Step 2: Check function return and parameter usage

   fun operate(x: Int, f: (Int) -> Int): Int { return f(x) } returns Int and calls f(x) properly. fun operate(x: Int, f: Int): Int { return f(x) } treats f as Int, not a function. fun operate(x: Int, f: (Int) Int): Int { return f(x) } misses arrow. fun operate(x: Int, f: (Int) -> Int) { return f(x) } lacks return type.

3. Final Answer:

   fun operate(x: Int, f: (Int) -> Int): Int { return f(x) } -> Option C

4. Quick Check:

   Function type syntax = (Int) -> Int [OK]

Hint: Look for (Type) -> ReturnType syntax for function parameters [OK]

Common Mistakes:

• Omitting the arrow '->' in function type
• Using wrong parameter type instead of function type
• Missing return type in function declaration

3. What is the output of this Kotlin code?

fun applyTwice(x: Int, f: (Int) -> Int): Int {
    return f(f(x))
}

fun increment(n: Int) = n + 1

fun main() {
    println(applyTwice(3, ::increment))
}

medium

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Understand applyTwice function behavior

   applyTwice calls the function f twice on x: f(f(x)). Here, f is increment which adds 1.

2. Step 2: Calculate the output step-by-step

   First increment(3) = 4, then increment(4) = 5, so applyTwice(3, increment) returns 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Increment twice on 3 = 5 [OK]

Hint: Apply the function twice stepwise to find output [OK]

Common Mistakes:

• Applying function only once
• Confusing function call syntax
• Ignoring the nested function call

4. Identify the error in this Kotlin higher-order function declaration:

fun transform(x: Int, f: Int -> Int): Int {
    return f(x)
}

medium

A. Missing parentheses around function type parameter

B. Return type of transform is missing

C. Function parameter name is invalid

D. Function body syntax is incorrect

Solution

1. Step 1: Check function type syntax in parameter

   Function types must be enclosed in parentheses like (Int) -> Int. Here, f: Int -> Int is missing parentheses.

2. Step 2: Verify other parts of the function

   Return type Int is present, parameter name f is valid, and function body syntax is correct.

3. Final Answer:

   Missing parentheses around function type parameter -> Option A

4. Quick Check:

   Function type needs parentheses: (Int) -> Int [OK]

Hint: Always wrap function types in parentheses (Type) -> ReturnType [OK]

Common Mistakes:

• Omitting parentheses around function type
• Confusing parameter name with type
• Missing return type declaration

5. How would you declare a Kotlin higher-order function named compose that takes two functions f and g (both from Int to Int) and returns a new function from Int to Int that applies g then f?

hard

A. fun compose(f: (Int) -> Int, g: (Int) -> Int): Int = f(g(0))

B. fun compose(f: Int, g: Int): Int = { x -> f(g(x)) }

C. fun compose(f: (Int) -> Int, g: (Int) -> Int): (Int) -> Int = f(g)

D. fun compose(f: (Int) -> Int, g: (Int) -> Int): (Int) -> Int = { x -> f(g(x)) }

Solution

1. Step 1: Understand function composition signature

   compose takes two functions f and g, both (Int) -> Int, and returns a function (Int) -> Int.

2. Step 2: Check the lambda expression for composition

   The returned function applies g first, then f: { x -> f(g(x)) }. fun compose(f: (Int) -> Int, g: (Int) -> Int): (Int) -> Int = { x -> f(g(x)) } matches this exactly.

3. Final Answer:

   fun compose(f: (Int) -> Int, g: (Int) -> Int): (Int) -> Int = { x -> f(g(x)) } -> Option D

4. Quick Check:

   Compose = return lambda applying g then f [OK]

Hint: Return a lambda applying g then f: { x -> f(g(x)) } [OK]

Common Mistakes:

• Returning wrong type instead of function
• Using incorrect parameter types
• Trying to call functions instead of returning a lambda