In variance (contravariance) in Kotlin - Time & Space Complexity

Time Complexity: In variance (contravariance)

O(n)

Understanding Time Complexity

Let's explore how the time cost changes when using in variance (contravariance) in Kotlin generics.

We want to see how the program's work grows as input size changes when using contravariant types.

Scenario Under Consideration

Analyze the time complexity of the following Kotlin code using in variance.

interface Consumer {
    fun consume(item: T)
}

fun feedAll(consumer: Consumer, items: List) {
    for (item in items) {
        consumer.consume(item)
    }
}
    

This code feeds a list of integers to a consumer that accepts numbers using contravariance.

Identify Repeating Operations

Look for loops or repeated actions that affect time.

• Primary operation: The for loop calling consume for each item.
• How many times: Once for every item in the items list.

How Execution Grows With Input

As the number of items grows, the loop runs more times, so work grows directly with input size.

Input Size (n)	Approx. Operations
10	10 consume calls
100	100 consume calls
1000	1000 consume calls

Pattern observation: The work increases in a straight line as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly with the number of items to consume.

Common Mistake

[X] Wrong: "Using in variance changes how many times the loop runs or makes it slower."

[OK] Correct: The variance only affects type safety and compatibility, not how many times the loop executes.

Interview Connect

Understanding how variance affects code helps you reason about type safety and performance separately, a useful skill in real projects.

Self-Check

What if we changed Consumer<Number> to Consumer<Any>? How would the time complexity change?

Practice

1. What does the in keyword mean when used in Kotlin generics?

easy

A. It marks a generic type as contravariant, allowing it to accept supertypes safely.

B. It marks a generic type as covariant, allowing it to produce subtypes safely.

C. It restricts a generic type to only accept exact types, no subtypes or supertypes.

D. It means the generic type can be used both as input and output without restrictions.

Solution

1. Step 1: Understand variance keywords in Kotlin generics

   Kotlin uses in for contravariance and out for covariance.

2. Step 2: Identify the meaning of in

   in means the generic type can accept supertypes safely as input but cannot produce output of that type.

3. Final Answer:

   It marks a generic type as contravariant, allowing it to accept supertypes safely. -> Option A

4. Quick Check:

   in = contravariant = accept supertypes [OK]

Hint: Remember: 'in' means input only, contravariant [OK]

Common Mistakes:

• Confusing 'in' with 'out' variance
• Thinking 'in' allows output of the generic type
• Assuming 'in' restricts to exact types only

2. Which of the following is the correct syntax to declare a contravariant generic interface in Kotlin?

easy

A. interface Consumer { fun consume(item: T) }

B. interface Consumer { fun consume(item: T) }

C. interface Consumer<T> { fun consume(item: in T) }

D. interface Consumer<T> { fun consume(item: out T) }

Solution

1. Step 1: Recall syntax for contravariant generic declaration

   Contravariance uses in before the generic type parameter in the interface declaration.

2. Step 2: Check method parameter usage

   Method parameter can use the generic type normally; the variance is declared at the interface level.

3. Final Answer:

   interface Consumer { fun consume(item: T) } -> Option B

4. Quick Check:

   Contravariant syntax = in before T [OK]

Hint: Use 'in' before generic type name for contravariance [OK]

Common Mistakes:

• Using 'out' instead of 'in' for contravariance
• Placing 'in' inside method parameters incorrectly
• Omitting variance keyword entirely

3. Consider the following Kotlin code:

interface Consumer {
    fun consume(item: T)
}

fun feed(consumer: Consumer<Number>) {
    consumer.consume(42)
}

val intConsumer: Consumer<Int> = object : Consumer<Int> {
    override fun consume(item: Int) {
        println("Consumed: $item")
    }
}

feed(intConsumer)

What will happen when this code runs?

medium

A. Prints 'Consumed: 42' successfully.

B. Runtime error due to type mismatch.

C. Compilation error because Consumer<Int> is not a subtype of Consumer<Number>.

D. Prints nothing because consume is never called.

Solution

1. Step 1: Understand contravariance direction

   Contravariance means Consumer<Supertype> can accept Consumer<Subtype>, not the other way around.

2. Step 2: Analyze the call feed(intConsumer)

   feed expects Consumer<Number>, but intConsumer is Consumer<Int>. Since Int is subtype of Number, Consumer<Int> is not subtype of Consumer<Number> when contravariant.

3. Final Answer:

   Compilation error because Consumer<Int> is not a subtype of Consumer<Number>. -> Option C

4. Quick Check:

   Contravariance reverses subtype relation [OK]

Hint: Contravariant: Consumer<Super> accepts Consumer<Sub>, not vice versa [OK]

Common Mistakes:

• Assuming Consumer<Int> can be passed where Consumer<Number> is expected
• Confusing covariance and contravariance
• Expecting runtime error instead of compile-time error

4. Given this Kotlin code snippet:

interface Consumer {
    fun consume(item: T)
}

fun process(consumer: Consumer<Number>) {
    consumer.consume(3.14)
}

val doubleConsumer: Consumer<Double> = object : Consumer<Double> {
    override fun consume(item: Double) {
        println("Consumed double: $item")
    }
}

process(doubleConsumer)

Why does this code cause a compilation error?

medium

A. Because Consumer<Double> cannot be passed where Consumer<Number> is expected due to contravariance.

B. Because Double is not a subtype of Number.

C. Because consume method parameter type is incorrect.

D. Because process function tries to consume an Int instead of a Double.

Solution

1. Step 1: Recall contravariance subtype rules

   For Consumer, Consumer<Supertype> can accept Consumer<Subtype>, not the reverse.

2. Step 2: Check the types in the call

   process expects Consumer<Number>, but doubleConsumer is Consumer<Double>. Double is subtype of Number, so Consumer<Double> is not subtype of Consumer<Number>.

3. Final Answer:

   Because Consumer<Double> cannot be passed where Consumer<Number> is expected due to contravariance. -> Option A

4. Quick Check:

   Contravariance reverses subtype relation [OK]

Hint: Contravariant types reverse subtype order [OK]

Common Mistakes:

• Thinking Double is not subtype of Number
• Confusing method parameter types
• Assuming runtime error instead of compile-time

5. You want to create a function that accepts any consumer that can consume Number or any of its supertypes safely. Which declaration correctly uses contravariance to allow this flexibility?

interface Consumer {
    fun consume(item: T)
}

fun acceptConsumer(consumer: Consumer<___>) {
    consumer.consume(100)
}

hard

A. Nothing

B. Number

C. Int

D. Any

Solution

1. Step 1: Understand contravariance usage

   Contravariance allows passing a consumer of a supertype to a function expecting a consumer of a subtype.

2. Step 2: Determine the correct generic type

   To accept consumers that can consume Number or any supertype safely (i.e., Consumer<Number> and Consumer<Any>), use Any as the generic parameter.

3. Final Answer:

   Any -> Option D

4. Quick Check:

   Contravariant consumer accepts supertypes [OK]

Hint: Use Any (a supertype of Number) for contravariant parameter to accept consumers of Number or its supertypes [OK]

Common Mistakes:

• Using supertype like Any, which only accepts Consumer<Any>
• Using subtype like Int
• Using Nothing which is subtype of all types