Extensions on built-in types in Kotlin - Time & Space Complexity

Time Complexity: Extensions on built-in types

O(n)

Understanding Time Complexity

When we add new functions to built-in types in Kotlin, it's important to see how fast these functions run.

We want to know how the time to run these extensions changes as the input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun String.countVowels(): Int {
    var count = 0
    for (char in this) {
        if (char.lowercaseChar() in "aeiou") {
            count++
        }
    }
    return count
}

val text = "Hello Kotlin Extensions"
println(text.countVowels())
    

This code adds a function to count vowels in any string by checking each character.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character in the string (length of the string).

How Execution Grows With Input

As the string gets longer, the function checks more characters one by one.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows directly with the string length; double the length, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to count vowels grows in a straight line with the string size.

Common Mistake

[X] Wrong: "Extensions always add extra time because they are special functions."

[OK] Correct: Extensions run like normal functions; their speed depends on what they do, not that they are extensions.

Interview Connect

Understanding how your extension functions perform helps you write clean and efficient code, a skill valued in real projects and interviews.

Self-Check

"What if we changed the extension to count vowels only in the first half of the string? How would the time complexity change?"