LESSON 212 OF 414 · BIG O NOTATION

Introduction to Logarithms in Scala: Array and String Costs

Watch the lesson

Next lesson

SCALA · BIG O NOTATION

Introduction To Logarithm in Scala, explained

What a logarithm tells you

A logarithm answers the question "how many times can I halve this number before I reach 1?". In Big O notation log n means the base-2 logarithm, and O(log n) describes an algorithm whose number of steps grows by one each time the input doubles.

You can see it with a loop that halves a value until it reaches 1 and counts the halvings:

def halvings(n: Int): Int = {
  var m = n
  var steps = 0
  while (m > 1) {
    m /= 2
    steps += 1
  }
  steps
}

Integer division truncates, so the count is the whole number of halvings:

halvings(1000)       = 9
halvings(1000000)    = 19
halvings(1000000000) = 29

A thousand times more input adds only about ten steps. That is why O(log n) is so much better than O(n) for large inputs: a billion elements need roughly thirty steps, not a billion.

Where logarithms appear in code

Any algorithm that throws away a constant fraction of the remaining work on each step is logarithmic. The classic case is binary search on a sorted Array[Int]: compare with the middle element and discard the half that cannot contain the target.

def binarySearch(a: Array[Int], target: Int): Int = {
  var lo = 0
  var hi = a.length - 1
  while (lo <= hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) == target) return mid
    else if (a(mid) < target) lo = mid + 1
    else hi = mid - 1
  }
  -1
}

On an array of one million sorted even numbers, looking for a value that is not there takes 20 probes, which matches the log of a million. A linear scan would need a million comparisons for the same answer. Binary search only works because the array is sorted; on unsorted data there is nothing to discard.

Digit counting works the same way: the number of times you can divide n by 10 before it reaches 0 is the number of digits, which grows with log n. Sorting methods such as sorted are O(n log n) for a related reason: they split the data in half about log n times and do O(n) work at each level.

Costs of common Array and String methods

Knowing what each built-in call costs lets you add up the cost of a whole function. Here n is the length of the array or string.

Operation	Cost	Notes
`arr(i)`, `arr(i) = x`, `s(i)`	`O(1)`	direct access by index
`arr.length`, `s.length`	`O(1)`	the size is stored
`arr.contains(x)`, `s.indexOf(c)`, `s.contains(t)`	`O(n)`	may scan everything
`arr.sum`, `arr.max`, `arr.map(f)`, `s.reverse`	`O(n)`	visit every element once
`arr :+ x`, `arr ++ other`	`O(n)`	build a new array
`buf += x` on an `ArrayBuffer`	`O(1)` amortized	occasionally the buffer resizes
`arr.sorted`	`O(n log n)`	returns a new sorted array

The Scala collections add a few differences worth remembering. An Array has a fixed size, so "adding" an element with :+ copies the whole array into a new one. A List is a linked list: x :: list and list.head take O(1), but list(i) has to walk i links, so it is O(n). Indexing a List inside a loop therefore makes the loop quadratic.

Adding costs together

Put the costs together by following the structure of the code. Statements one after another add; a call inside a loop multiplies by the number of iterations.

A loop over arr with only O(1) work inside is O(n).
A loop over arr that calls arr.contains(x) each time is O(n * n), because contains is itself O(n).
Calling sorted once and then binary searching for each element is O(n log n) for the sort plus O(n log n) for the searches, so O(n log n) overall.

Common mistakes

Binary search on unsorted data. The halving only works when the order tells you which half to keep.
Forgetting hidden loops. contains, indexOf and reverse look like one step but each walks the data.
Treating sorted as in place. It returns a new array and leaves the original unchanged: sorting Array(5, 3, 8, 1) gives a new array 1,3,5,8, while the original still reads 5,3,8,1.
Mixing up the base. In Big O the base of the logarithm does not matter, because changing the base only multiplies by a constant.

Key takeaways

log n counts how many times you can halve n; a billion needs only about 30 halvings.
Binary search is O(log n) and needs sorted input.
Indexing and length are O(1); searching, copying and reversing are O(n); sorting is O(n log n).
Check the collection type: list(i) on a List is O(n), while arr(i) on an Array is O(1).

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free