Multiple type parameters in Kotlin - Time & Space Complexity

Time Complexity: Multiple type parameters

O(n * m)

Understanding Time Complexity

When using multiple type parameters in Kotlin, we want to understand how the program's work grows as input sizes change.

We ask: how does the time needed change when the inputs for each type grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun <A, B> pairElements(listA: List<A>, listB: List<B>): List<Pair<A, B>> {
    val result = mutableListOf<Pair<A, B>>()
    for (a in listA) {
        for (b in listB) {
            result.add(Pair(a, b))
        }
    }
    return result
}
    

This function creates pairs from every element in listA with every element in listB.

Identify Repeating Operations

• Primary operation: Nested loops over listA and listB.
• How many times: Outer loop runs once per element in listA; inner loop runs once per element in listB for each outer loop.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
listA = 10, listB = 10	100
listA = 100, listB = 100	10,000
listA = 1000, listB = 1000	1,000,000

Pattern observation: The total work grows by multiplying the sizes of both lists.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows by multiplying the size of the first list (n) by the size of the second list (m).

Common Mistake

[X] Wrong: "The time grows only with the size of one list because the other is just a type parameter."

[OK] Correct: Both lists have real sizes that affect the loops. The type parameters only name the types, but the loops run over actual elements, so both sizes matter.

Interview Connect

Understanding how multiple inputs affect time helps you explain your code clearly and shows you can think about efficiency in real situations.

Self-Check

"What if we changed the inner loop to only run a fixed number of times regardless of listB's size? How would the time complexity change?"

Practice

1. What does it mean when a Kotlin function has <T, U> before its name?

easy

A. The function is limited to only one type parameter named T or U.

B. The function can only accept types T or U but not both at the same time.

C. The function uses two different type parameters, T and U, to work with multiple types.

D. The function automatically converts types T and U to String.

Solution

1. Step 1: Understand type parameters in Kotlin

   Type parameters like <T, U> allow a function to accept multiple types, making it flexible.

2. Step 2: Interpret the meaning of <T, U>

   Having <T, U> means the function can work with two different types, T and U, independently.

3. Final Answer:

   The function uses two different type parameters, T and U, to work with multiple types. -> Option C

4. Quick Check:

   Multiple type parameters = flexible function types [OK]

Hint: Multiple type parameters mean multiple flexible types [OK]

Common Mistakes:

• Thinking it limits to only one type at a time
• Assuming automatic type conversion happens
• Confusing type parameters with actual types

2. Which of the following is the correct syntax to declare a Kotlin function with two type parameters named T and U?

easy

A. fun myFunction(param1: T, param2: U) {}

B. fun myFunction(param1: T, param2: U) {}

C. fun myFunction(param1: T, param2: U) {}

D. fun myFunction(param1: T, param2: U) {}

Solution

1. Step 1: Recall Kotlin generic function syntax

   Type parameters are declared immediately after the fun keyword inside angle brackets, separated by commas.

2. Step 2: Check each option's syntax

   fun myFunction(param1: T, param2: U) {} correctly uses <T, U> after fun and before the function name, matching Kotlin syntax.

3. Final Answer:

   fun <T, U> myFunction(param1: T, param2: U) {} -> Option A

4. Quick Check:

   Type parameters go after fun with commas [OK]

Hint: Type parameters come right after fun, separated by commas [OK]

Common Mistakes:

• Missing comma between type parameters
• Placing type parameters after function name
• Putting type parameters after parameter list

3. What is the output of this Kotlin code?

fun <T, U> pairToString(pair: Pair<T, U>): String {
    return "${pair.first} and ${pair.second}"
}

fun main() {
    val result = pairToString(Pair(10, "cats"))
    println(result)
}

medium

A. Compilation error

B. Pair(10, cats)

C. cats and 10

D. 10 and cats

Solution

1. Step 1: Understand the function behavior

   The function takes a Pair with types T and U, then returns a string combining first and second values.

2. Step 2: Trace the main function call

   pairToString is called with Pair(10, "cats"), so pair.first = 10 and pair.second = "cats".

3. Final Answer:

   10 and cats -> Option D

4. Quick Check:

   pair.first + " and " + pair.second = "10 and cats" [OK]

Hint: Read pair.first and pair.second values carefully [OK]

Common Mistakes:

• Swapping first and second values
• Expecting Pair's default toString output
• Thinking it causes a compilation error

4. Identify the error in this Kotlin function declaration:

fun <T, U> combine(a: T, b: U): T {
    return b
}

medium

A. Return type T does not match returned value b of type U.

B. Missing comma between T and U in type parameters.

C. Function must return type U instead of T.

D. No error, the function is correct.

Solution

1. Step 1: Check function return type and return statement

   The function declares return type T but returns b which is of type U.

2. Step 2: Understand type mismatch error

   Returning U where T is expected causes a type mismatch compilation error.

3. Final Answer:

   Return type T does not match returned value b of type U. -> Option A

4. Quick Check:

   Return type must match returned value type [OK]

Hint: Return type must match the returned value type [OK]

Common Mistakes:

• Ignoring type mismatch between T and U
• Assuming Kotlin auto-converts types
• Missing comma in type parameters (not the case here)

5. You want to create a Kotlin generic class Box that can hold two different types of items, T and U. Which of the following class declarations correctly uses multiple type parameters and allows storing and retrieving both items?

hard

A. class Box<T>(val first: T, val second: T) {
fun getFirst(): T = first
fun getSecond(): T = second
}

B. class Box(val first: T, val second: U) {
fun getFirst(): T = first
fun getSecond(): U = second
}

C. class Box {
val first: T
val second: U
}

D. class Box(val first: T, val second: U) {
fun getFirst(): T = first
fun getSecond(): U = second
}

Solution

1. Step 1: Check correct multiple type parameter declaration

   class Box(val first: T, val second: U) { fun getFirst(): T = first fun getSecond(): U = second } declares class Box with <T, U> and constructor parameters of types T and U, which is correct.

2. Step 2: Verify methods to retrieve both items

   class Box(val first: T, val second: U) { fun getFirst(): T = first fun getSecond(): U = second } provides getFirst() returning T and getSecond() returning U, matching stored types.

3. Final Answer:

   class Box<T, U>(val first: T, val second: U) { fun getFirst(): T = first fun getSecond(): U = second } -> Option B

4. Quick Check:

   Multiple type parameters with matching properties and methods [OK]

Hint: Use and matching properties for both types [OK]

Common Mistakes:

• Using only one type parameter for both items
• Not declaring type parameters in class header
• Using undefined types without generics