Time Complexity: Equality (== structural vs === referential)
O(n)
0
0
Equality (== structural vs === referential) in Kotlin - Performance Comparison
Understanding Time Complexity
When checking if two things are equal in Kotlin, there are two ways: structural and referential equality.
We want to understand how the time it takes to check equality changes as the data grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
val list1 = listOf(1, 2, 3, 4, 5)
val list2 = listOf(1, 2, 3, 4, 5)
// Structural equality check
val structuralEqual = list1 == list2
// Referential equality check
val referentialEqual = list1 === list2
This code compares two lists using structural equality (==) and referential equality (===).
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Structural equality (==) compares each element one by one.
- How many times: It checks elements up to the size of the lists.
- Referential equality (===) just checks if both variables point to the same object once.
How Execution Grows With Input
Structural equality checks each element, so more elements mean more work.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 element comparisons |
| 100 | 100 element comparisons |
| 1000 | 1000 element comparisons |
Pattern observation: The work grows directly with the number of elements.
Final Time Complexity
Time Complexity: O(n)
This means the time to check structural equality grows in a straight line with the size of the data.
Common Mistake
[X] Wrong: "Checking structural equality is always as fast as referential equality."
[OK] Correct: Structural equality compares each element, so it takes longer as data grows, unlike referential equality which just checks if two variables point to the same object.
Interview Connect
Understanding how equality checks work helps you write efficient code and explain your choices clearly in interviews.
Self-Check
"What if the lists contain other lists inside? How would that affect the time complexity of structural equality?"