Why slicing and concatenation are not free
Reading one element with arr(i) takes constant time. Taking a piece of a collection or joining two of them is different, because Scala builds a new collection and copies the elements into it. The work grows with the number of elements copied, so a single innocent-looking line can hide a loop.
Slicing
Scala slices arrays, strings and lists with the methods slice(from, until), take(n) and drop(n). For strings there is also substring(from, until). The upper bound is excluded, and slice, take and drop clamp out-of-range bounds instead of throwing.
val arr = Array(10, 20, 30, 40, 50)
println(arr.slice(1, 4).mkString(",")) // 20,30,40
println(arr.take(2).mkString(",") + " " + arr.drop(3).mkString(",")) // 10,20 40,50
val s = "algorithm"
println(s.substring(2, 5) + " " + s.take(4) + " " + s.drop(6)) // gor algo thm
println(s.slice(0, 100)) // algorithm
A slice of k elements costs O(k), since it copies those k elements. Taking the whole array with arr.slice(0, n), or drop(1) on a large array, therefore costs O(n).
The copy is independent of the original. Changing an element of a slice does not change the source array:
val sliced = arr.slice(1, 4)
sliced(0) = 99
println(arr(1)) // 20
Slicing a List also depends on where the slice lies: take(k) walks k links, and drop(k) walks k links and then shares the rest of the list, so a large drop costs O(k) even though no elements are copied.
Concatenation
Joining two arrays with ++ creates a new array of size a.length + b.length, so it costs O(a.length + b.length). The inputs are not modified:
val a = Array(1, 2)
val b = Array(3, 4)
println((a ++ b).mkString(",")) // 1,2,3,4
println(a.mkString(",")) // 1,2
The same holds for strings: "abc" + "def" creates a new 6-character string, copying both operands. A String cannot be changed after it is created, so there is no way to extend one in place. Adding one element to an Array with :+ is the same copy, so it costs O(n).
The trap: concatenating inside a loop
Because every + copies, building a string one piece at a time in a loop does more and more copying:
var text = ""
for (i <- 1 to 5) text += i
println(text) // 12345
On iteration k the string has about k characters, and it is copied again to add one more. The total is 1 + 2 + ... + n, which is O(n²) characters copied for n appends, even though the code looks like a single loop.
The fix is a mutable builder, whose appends take amortized O(1), so the loop as a whole is O(n):
val sb = new StringBuilder
for (i <- 1 to 5) sb.append(i)
println(sb.toString) // 12345
For collections, scala.collection.mutable.ArrayBuffer plays the same role: buf += x is amortized O(1), and you convert at the end with toArray or toList, which is one O(n) copy. Repeating result = result ++ other in a loop is quadratic for the same reason as the string case.
Summary of costs
| Operation | Cost |
|---|---|
arr(i), s(i) | O(1) |
arr.slice(i, j), s.substring(i, j) | O(j - i) |
arr.take(k), arr.drop(k) | proportional to the size of the result |
a ++ b, s + t | O(len(a) + len(b)) |
arr :+ x | O(n) |
appending to StringBuilder or ArrayBuffer | O(1) amortized |
appending n times with + or ++ | O(n²) total |
Common mistakes
- Slicing inside a loop. Recursive code that calls
arr.drop(1)on every call copiesn - 1,n - 2, ... elements, which isO(n²)in total. Pass index bounds instead of making new slices. - Assuming a slice is a view. On arrays and strings,
slicecopies. Writing to the slice leaves the source untouched. - Counting a concatenation as
O(1). It always costs the combined length. - Appending to a
Listwith:+in a loop. Appending to the end of an immutable list walks the whole list, sonappends areO(n²). Prepend with::and reverse once at the end, or use anArrayBuffer.
Key takeaways
- Slicing and concatenation copy elements, so they cost time proportional to the size of the result.
- Repeated
+on strings or++on arrays in a loop isO(n²). - Use
StringBuilderorArrayBufferto build results piece by piece inO(n). - Prefer index bounds over repeated slicing when you only need to look at part of a collection.
