Why slicing and concatenation need a second look
Some operations look like a single step but copy data behind the scenes. Taking part of a string, joining two strings and building a list piece by piece are all common in loops, and their cost decides whether a loop is O(n) or O(n²). This reading shows what each operation costs in Kotlin so you can count it correctly in Big O.
The rule behind everything below: an operation that copies k elements costs O(k), however short the line that triggers it.
Slicing strings
A substring is a new string. substring(start, end) copies the characters between the two indices, so the cost grows with the length of the piece, not with the length of the original:
val s = "AlgoCademy"
println(s.substring(0, 3)) // Alg
println(s.substring(4)) // Cademy
println(s.take(4) + s.drop(4)) // AlgoCademy
The output is Alg, Cademy and AlgoCademy. The helpers take(k), drop(k) and substring all copy what they return. Taking the first 3 characters is O(1) work in practice because 3 is a constant, but s.substring(1) copies n - 1 characters and is O(n).
This matters when a loop slices on every iteration. Calling s.substring(i) for each i from 0 to n - 1 copies about n + (n - 1) + ... + 1 characters, which is roughly n²/2, so the loop is O(n²) even though its body is one line. Indexing with s[i] copies nothing and costs O(1), so comparing characters by index is the cheaper way to walk a string.
Slicing lists
Lists behave differently depending on the call:
list.subList(from, to)returns a view of the same elements, not a copy, so creating it isO(1). It prints like a list:listOf(1, 2, 3, 4, 5, 6).subList(1, 4)gives[2, 3, 4].list.slice(1..3)andlist.drop(2)build new lists. They give[2, 3, 4]and[3, 4, 5, 6], and they costO(k)for thekelements they return.list + listOf(7)builds a new list holding every element of both, so it costsO(n): the result is[1, 2, 3, 4, 5, 6, 7].
Arrays follow the same idea: copyOfRange and sliceArray copy, and each costs the size of the piece.
Concatenation
A Kotlin String can't be changed after it is created. So result += "x" doesn't append in place: it builds a brand new string with the old characters plus the new one and makes result point to it. Joining a string of length a with one of length b costs O(a + b).
Consider this function:
fun repeatConcat(n: Int): String {
var result = ""
for (i in 0 until n) {
result += "x"
}
return result
}
On iteration i the string has i characters, and the join copies all of them. The total number of characters copied is 0 + 1 + 2 + ... + (n - 1), which is about n²/2. That is O(n²), although the loop runs only n times.
A StringBuilder is a growable buffer, and appending to it adds to the end without recopying everything:
fun repeatBuilder(n: Int): String {
val sb = StringBuilder()
for (i in 0 until n) {
sb.append("x")
}
return sb.toString()
}
Each append costs O(1) on average, and the single toString() at the end copies the n characters once. The total is O(n), and both functions return the same text: repeatConcat(5) == repeatBuilder(5) is true.
A JVM compiler may optimise a single + expression such as a + " " + b into one join. That helps inside one statement, but it can't remove the copying when you grow a string across loop iterations.
Growing a list is cheap
Adding to the end of a MutableList with add is O(1) on average. The list keeps spare capacity and occasionally grows it, and the cost of those rare growth steps averages out. Building a list of n elements with add is therefore O(n). Writing list = list + item in a loop is a different story: each + creates a new list and copies the old one, which gives the same O(n²) as string concatenation.
Counting the cost of a function
To find the complexity, ask for every line whether it copies data, and how much:
- Indexing, comparing two characters, and adding two numbers cost
O(1). - A slice, a join, a conversion from one collection type to another and
toString()costO(k)for the number of elements copied. - Multiply the cost of a line by the number of times the loop runs it.
- Add the loops together and keep the biggest term.
Applying this to the string-slicing loop gives n iterations times up to n copied characters, so O(n²). Applying it to the StringBuilder version gives n iterations times O(1), plus one final copy, so O(n).
Key takeaways
- A slice or a join copies, so its cost is the size of the result. The exception is
subList, which is a view. - Strings are immutable. Building one with
+=in a loop isO(n²); use aStringBuilderto getO(n). addon aMutableListisO(1)on average, butlist + itemcopies the whole list.- When a loop body has a hidden copy, multiply that copy's cost by the number of iterations.