Why built-ins need a cost
A single line of Scala can hide a whole loop. When you write nums.contains(8) or list.length, the library does the looping for you, but the work still counts toward your solution's time complexity. If you call such a method inside your own loop, the costs multiply. Knowing what the common methods cost keeps you from writing an O(n²) solution that looks like O(n).
Array
An array is a fixed-size block of memory, so reaching an element by position is quick, and anything that has to look at every element costs O(n).
| Operation | Example | Time |
|---|---|---|
| Read or write by index | nums(i), nums(i) = 5 | O(1) |
| Size | nums.size | O(1) |
| Search for a value | nums.contains(8), nums.indexOf(8) | O(n) |
| Largest or smallest | nums.max, nums.min | O(n) |
| Total | nums.sum | O(n) |
| Reverse (new array) | nums.reverse | O(n) |
| Sort (new array) | nums.sorted | O(n log n) |
| Copy a part | nums.slice(1, 3), nums.take(2) | O(k) for k elements |
For val a = Array(5, 3, 8), a.contains(8) is true, a.indexOf(8) is 2, a.sum is 16, a.max is 8, and a.sorted.toList is List(3, 5, 8). Each of the O(n) calls walks the array from the start. The methods reverse and sorted return new arrays and leave a as it was.
ArrayBuffer
An ArrayBuffer is a growable array. Indexing and size behave like an array. Adding at the end with += is constant time on average. Inserting or removing near the front is O(n), because every later element has to shift over by one place.
List
A List is a linked chain of cells, and that changes which operations are cheap:
| Operation | Example | Time |
|---|---|---|
| Add at the front | 0 :: list | O(1) |
| First element, rest | list.head, list.tail | O(1) |
| Add at the end | list :+ 4 | O(n) |
| Element at a position | list(i) | O(i) |
| Length | list.length, list.size | O(n) |
| Last element | list.last | O(n) |
Two of these surprise people. First, list.length counts the cells each time you call it. Second, list(i) in a loop makes the loop quadratic: for (i <- list.indices) { list(i) } walks 0 + 1 + 2 + ... cells in total, which is O(n²). For indexed access, copy the list into an array with toArray once, or loop over the elements directly.
Set and Map
| Operation | Example | Time |
|---|---|---|
| Membership test | set.contains(2) | O(1) on average |
| Look up a key | map("a"), map.get("a") | O(1) on average |
| Add or update an entry | map + ("b" -> 2) | O(1) on average |
With val m = Map("a" -> 1), m.get("a") returns Some(1), m.get("z") returns None and m.getOrElse("z", 0) returns 0. By contrast, m("z") throws an exception for a missing key. A hash-based set or map is the standard way to replace a repeated O(n) search with an average O(1) check. Converting an array to a set with toSet is one O(n) pass.
Strings
A string's length is O(1) and reading one character with s(i) is O(1). Building a new string, as s + "d" does, copies the characters, so it costs O(n) for a string of length n. Doing that inside a loop adds up to O(n²) for long results.
Transforming whole collections
Methods that produce a new collection from every element, such as map, filter, toList and mkString, are O(n): they visit each element once. a.toList.map(_ * 2) returns List(10, 6, 16) for the array above, after two passes.
How to reason about a call
- Ask whether the method has to look at every element. If so it is at least
O(n). - Multiply by the loops around it. A
containson an array, inside a loop overnelements, givesO(n²). - Add, don't multiply, for steps one after another. A sort followed by a single scan is
O(n log n)plusO(n), which isO(n log n). - Replace a repeated search with a set or a map when the structure allows it.
Key takeaways
- Array indexing and size are
O(1); searching, summing and reversing areO(n); sorting isO(n log n). - A
Listis cheap at the front and expensive for length, indexing and appending at the end. - Hash-based sets and maps answer lookups in constant time on average.
- A built-in call inside a loop multiplies its cost by the number of passes.
