Why built-ins need counting too
A single line such as list.contains(x) or nums.sorted() looks like one step, but the library does a loop for you. When you work out a solution's complexity, each library call counts as the work it actually does. A loop that runs n times and calls an O(n) function on each pass is O(n²), even though only one loop is visible.
This reading lists what common Kotlin functions cost. The costs are for the standard library on the JVM, and n is the number of elements in the collection the function is called on.
Lists: List, MutableList and ArrayList
mutableListOf() creates an ArrayList, which keeps its elements in a growable array.
| Operation | Time | Why |
|---|---|---|
list[i], list.size | O(1) | direct position in the array |
list[i] = x | O(1) | overwrites one slot |
list.add(x) | O(1) amortized | appends at the end; occasionally the array must grow |
list.removeLast() | O(1) | removes the last slot |
list.add(0, x), list.removeAt(0) | O(n) | every other element shifts by one |
list.contains(x), x in list, list.indexOf(x) | O(n) | scans until it finds a match |
list.remove(x) | O(n) | searches, then shifts |
list.sum(), list.max(), list.joinToString() | O(n) | visit every element |
list.map { }, list.filter { } | O(n) | one pass plus a new list |
list.reversed(), list.toList() | O(n) | build a copy |
list.sorted(), list.sort() | O(n log n) | comparison sort |
Arrays
An IntArray or Array<String> has a fixed size, so it offers the same constant-time arr[i], arr[i] = x and arr.size. Functions that read or copy everything are linear: sum(), max(), contains, indexOf, copyOf(), toList(), reversedArray(). Sorting is O(n log n): sorted() returns a new list and sort() sorts the array in place. binarySearch is O(log n), but it requires an array that is already sorted.
Maps and sets
| Operation | Time |
|---|---|
map[key], map[key] = value, key in map | O(1) on average |
set.add(x), x in set, set.remove(x) | O(1) on average |
Looping over map or set | O(n) |
mutableMapOf() and mutableSetOf() create hash-based collections. "On average" means that with a reasonable hash function the lookups spread out evenly. Missing keys are not an error: map["z"] returns null, in constant time.
Double-ended queues
Kotlin's ArrayDeque removes and adds at both ends in constant time (amortized): addFirst, addLast, removeFirst, removeLast. When code needs to take elements off the front repeatedly, it is a better fit than a list, where removeAt(0) is O(n).
Sorting and space
Time is only half of the picture. sorted() returns a new list, so it needs O(n) extra space as well as O(n log n) time. sort() on a MutableList or an array changes the original instead, which saves the copy but loses the original order. Likewise map, filter, reversed() and toList() each allocate a result as large as their output. When a problem asks for constant extra space, these calls are not allowed, even though each is a single line.
A hidden loop in action
Suppose you want to know whether an array has a duplicate. Here is a version that looks like a single loop:
fun hasDuplicate(nums: List<Int>): Boolean {
val seen = mutableListOf<Int>()
for (n in nums) {
if (n in seen) return true
seen.add(n)
}
return false
}
The loop runs up to n times, and n in seen scans a list, which is O(n), so the function is O(n²). Changing only the type of seen fixes it:
fun hasDuplicate(nums: List<Int>): Boolean {
val seen = mutableSetOf<Int>()
for (n in nums) {
if (n in seen) return true
seen.add(n)
}
return false
}
Now n in seen is O(1) on average, and the whole function is O(n) time with O(n) extra space. This is a typical trade: spend memory to save time.
Common mistakes
Most slow solutions come from one of the following patterns, and each is easy to avoid once you know the cost of the call.
- Treating a built-in as O(1). If the function must look at the elements, it is at least
O(n). - Calling
sorted()inside a loop. Sorting costsO(n log n)each time. Sort once, outside the loop. - Chaining many
mapandfiltercalls. Each makes a new list, soa.filter { }.map { }is stillO(n)but does two passes and two lists. The constant factor is higher; the complexity class is the same. - Using
removeAt(0)in a loop to drain a list. That isO(n²)overall; use anArrayDequeor an index.
Key takeaways
Before using a built-in inside a loop, ask what it costs per call and multiply by the number of calls.
- Index access and
sizeareO(1); searching a list or array isO(n); sorting isO(n log n). - Hash-based
MapandSetlookups areO(1)on average. - Add the hidden cost of each library call to the loops around it.