What constant time means
An operation runs in constant time, written O(1), when the number of steps doesn't depend on the size of the input. It takes the same work whether the array holds ten elements or ten million. Constant time is the best case for any operation, and a large part of designing fast solutions is finding ways to replace a loop with a constant-time step.
Constant-time operations in Scala
Arithmetic and comparisons
Adding, subtracting, multiplying, dividing, taking a remainder and comparing two Int or Long values each take one step, whatever the numbers are:
def isEven(n: Int): Boolean = n % 2 == 0
This method does the same work for 10 and for 1000000000.
Reading and writing an array element
An array stores its elements next to each other in memory, so Scala can compute where element i lives and jump straight to it. Reading nums(i) and writing nums(i) = value are both O(1), and so is asking for nums.size:
def lastElement(nums: Array[Int]): Int = nums(nums.size - 1)
For Array(4, 8, 15) this returns 15, and it takes the same few steps for an array of any length.
Looking up a key in a map
A Map finds the value for a key without scanning all the entries. With val ages = Map("Ana" -> 25, "Bob" -> 31), the call ages("Ana") returns 25, and ages.get("Zed") returns None. Lookups in Scala's standard hash-based Map and Set are effectively constant time. (They are constant on average rather than strictly guaranteed, since the cost depends on how well the keys spread out.)
Appending to a growable buffer
Adding an element at the end of an ArrayBuffer with += is constant time on average. Now and then the buffer runs out of room and copies itself into a bigger one, but those copies are rare enough that the cost averages out to a constant per append. This is called amortized constant time.
Replacing a loop with a formula
A classic way to get constant time is to find a formula for what a loop computes. The sum of the numbers from 1 to n can be computed by looping:
def sumLoop(n: Int): Int = {
var total = 0
for (i <- 1 to n) {
total += i
}
return total
}
That takes O(n) steps. The formula n * (n + 1) / 2 gives the same answer in a fixed number of steps:
def sumTo(n: Int): Int = n * (n + 1) / 2
Both return 5050 for n = 100. The loop does a hundred additions; the formula does one multiplication, one addition and one division. For n = 1000000000 the loop does a billion additions and the formula still does three operations.
Constant means a fixed number of steps, not one step
- Five steps is still
O(1). A method that does a dozen arithmetic operations is constant time as long as that number doesn't grow with the input. - A loop with a fixed bound is constant. A loop that always runs exactly 10 times does the same work for any input, so it is
O(1). A loop that runsnums.sizetimes isO(n). - Constant doesn't mean fast in absolute terms. It means the cost doesn't grow with the input.
Watch out for Int overflow
A formula that is fast can still be wrong when the numbers get big. Scala's Int has 32 bits, and overflow wraps around silently. With n = 70000 the true sum is 2450035000, which is more than the largest Int (2147483647). The formula sumTo returns 302551352 there, because n * (n + 1) overflows before the division, and the loop version returns -1844932296. Use Long when sums can exceed about two billion.
Key takeaways
O(1)means the number of steps doesn't depend on the input size.- Arithmetic, array indexing,
Array.sizeand map lookups are constant time. Appending to anArrayBufferis constant time on average. - A formula can replace a loop and turn
O(n)intoO(1). - A fixed number of steps is constant, even when that number is large.
- Constant time says nothing about overflow: pick a type that is wide enough.
